A stable sorting algorithm is one which preserves the order of duplicate key ent

Question

A stable sorting algorithm is one which preserves the order of duplicate key entries when sorted. In other words, if entries e1 and e2 have the same key k, and e1 appears before e2 in the input, then e1 will appear before e2 in the sorted output.

a) Is quicksort stable? Prove your answer, detailing every step that you take to arrive at the conclusion

b) Suppose you use radix sort to sort countries according to ascending order of population. The populations are read in as text, and digits are extracted using the Character.digit(char ch, int radix) method. What is the worst case number of unit time operations that would be performed to sort this list? State the unit time operations, and show the derivation of your result. (You may want to use the fact that there are about 190 countries, and China has the largest population, of around 1.3 billion.)

c) For the sorting problem described in (b), describe the fastest (in real time, not big O) possible implemenation you can think of. (Side note: Vatican City has a population of 800). Detail the data structure and the process. You can use any of the sorting algorithms (except radix sort, which you have already analyzed in part b).

Explanation / Answer

a)

Quicksort is not a stable alogorithm.

in a list if 10 8 6 10 5 1000 10 are there

then the 10 in 1st position may not be the first 10 present in the output after sorting. If there is a comparision between 1st 10 and 2nd 10 based on the pivot element. so ordering might change in the final output.so, selecting pivot is useful for ordering and also make sure that the copying of elements between the partitions never swaps the original order.

quick sort algorithm is not stable since it swaps equal elements.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.