The analysis of Quicksort programs

DOI10.1007/BF00289467zbMath0325.68016MaRDI QIDQ1225454

Robert Sedgewick

Publication date: 1977

Published in: Acta Informatica (Search for Journal in Brave)

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (26)

Optimizing sorting algorithms by using sorting networks ⋮ The impact of random initialization on the runtime of randomized search heuristics ⋮ Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme ⋮ A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries ⋮ Some properties of a limiting distribution in Quicksort ⋮ On Smoothed Analysis of Quicksort and Hoare’s Find ⋮ Analysis of quickselect : an algorithm for order statistics ⋮ Sorting numbers in linear expected time and optimal extra space ⋮ Sorting a linked list with equal keys ⋮ BlockQuicksort ⋮ Asymptotic distributions for random median quicksort ⋮ A fixed point theorem for distributions ⋮ Parallel distributive partitioned sorting methods ⋮ Analysis of swaps in radix selection ⋮ BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small) ⋮ A limiting distribution for quicksort ⋮ Applying Sorting Networks to Synthesize Optimized Sorting Libraries ⋮ On a multivariate contraction method for random recursive structures with applications to Quicksort ⋮ A limit theorem for “quicksort” ⋮ Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise ⋮ Sorting by distributive partitioning ⋮ Verified analysis of random binary tree structures ⋮ QuickXsort: a fast sorting scheme in theory and practice ⋮ A Machine-Checked Proof of the Average-Case Complexity of Quicksort in Coq ⋮ An efficient external sorting with minimal space requirement ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm

Uses Software

• Quicksort
• Find
• Algorithm 347

Cites Work

• Quicksort with Equal Keys
• Implementing Quicksort programs
• Some Theorems on Sorting
• Increasing the efficiency of quicksort
• Sorting in a paging environment
• Samplesort: A Sampling Approach to Minimal Storage Tree Sorting
• Quicksort
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The analysis of Quicksort programs