Sorting algorithms - Data Structures and Problem Solving Using Java - page 384

code to avoid some of the extra copying. Quicksort is tricky to code. Asymp-
totically, it has almost certain O ( N log N ) performance with a careful imple-
mentation, and we showed that this outcome is essentially as good as we can
expect. In Section 21.5 we discuss another popular internal sort, heapsort .
To test and compare the merits of the various sorting algorithms, we need
to be able to generate random inputs. Randomness is an important topic in
general, and we discuss it in Chapter 9.
key concepts
comparison-based sorting algorithm An algorithm that makes ordering deci-
sions only on the basis of comparisons. (353)
diminishing gap sort Another name for Shellsort. (358)
inversion A pair of elements that are out of order in an array. Used to mea-
sure unsortedness. (355)
lower-bound proof for sorting Confirms that any comparison-based sorting
algorithm must use at least roughly N log N comparisons on average and
in the worst case. (381)
median-of-three partitioning The median of the first, middle, and last elements
is used as the pivot. This approach simplifies the partitioning stage of
quicksort. (373)
mergesort A divide-and-conquer algorithm that obtains an O ( N log N ) sort. (361)
partition The step of quicksort that places every element except the pivot in
one of two groups, one consisting of elements that are smaller than or
equal to the pivot and one consisting of elements that are larger than or
equal to the pivot. (367)
pivot For quicksort, an element that divides an array into two groups; one that
is smaller than the pivot and one that is larger than the pivot. (367)
quickselect An algorithm used to perform a selection that is similar to quicksort
but makes only one recursive call. The average running time is linear. (380)
quicksort A fast divide-and-conquer algorithm when properly implemented; in many
situations it is the fastest comparison-based sorting algorithm known. (364)
selection The process of finding the k th smallest element of an array. (380)
Shellsort A subquadratic algorithm that works well in practice and is simple
to code. The performance of Shellsort is highly dependent on the incre-
ment sequence and requires a challenging (and not completely resolved)
analysis. (357)