If you are sorting a large list with many equal keys, then instead of partitioni

Question

If you are sorting a large list with many equal keys, then instead of partitioning the list into sublists that are less than, and greater than the pivot, it would be desirable if we could partition the sublist into three sublists, those less than, equal to, and greater than the pivot. The problem is writing a highly efficient partitioning procedure that does this and that doesn't do significantly more work than a conventional partitioning procedure does when the keys are all distinct. Can you come up with such a method?

Explanation / Answer

Three-way radix quicksort (developed by Sedgewick and also known as multikey quicksort): is a combination of radix sort and quicksort. Pick an element from the array (the pivot) and consider the first character (key) of the string (multikey). Partition the remaining elements into three sets: those whose corresponding character is less than, equal to, and greater than the pivot's character. Recursively sort the "less than" and "greater than" partitions on the same character. Recursively sort the "equal to" partition by the next character (key). Given we sort using bytes or words of length W bits, the best case is O(KN) and the worst case O(2KN) or at least O(N2) as for standard quicksort, given for unique keys N<2K, and K is a hidden constant in all standard comparison sort algorithms including quicksort. This is a kind of three-way quicksort in which the middle partition represents a (trivially) sorted subarray of elements that are exactly equal to the pivot.

refer this

http://www.drdobbs.com/database/sorting-strings-with-three-way-radix-qui/184410724

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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