patternMinor
Stability of QuickSort Algorithm
Viewed 0 times
stabilityalgorithmquicksort
Problem
Def: the stability of algorithm is defined in case of the algorithm preserves same value elements while sorting as the following shows:
So for this QuickSort algorithm:
Problem: We can make it stable by changing condition
So for this QuickSort algorithm:
public class QuickSort {
public static int[] sortedData;
public static void sort(int[] data, int low, int high){
sortedData = data;
int i = low;
int j = high;
int mid = low+(high-low)/2;
int pivot = data[mid];
if(i>j) return;
while(ipivot)
j--;
if(ii)
sort(data, i, high);
}
}Problem: We can make it stable by changing condition
while(i<=j) to while(i<j). What do you think please? What advantages this will bring please? It will reduce time by constant factor and $O(n)$ in worst case if all elements are equal other than that I am not sure what are the advantages of stability condition of algorithm please?Solution
One huge advantage of a stable sorting algorithm is that a user is able to first sort a table on one column, and then by another.
Say that you have a website like Wikipedia with some tabular data, say a list of sorting algorithms, two of the columns being year discovered and name. If you want that table sorted by year, and then alphabetically by name, you can sort the table first by name, then by year.
This is only guaranteed to work with stable sorting.
Say that you have a website like Wikipedia with some tabular data, say a list of sorting algorithms, two of the columns being year discovered and name. If you want that table sorted by year, and then alphabetically by name, you can sort the table first by name, then by year.
This is only guaranteed to work with stable sorting.
Context
StackExchange Computer Science Q#144424, answer score: 9
Revisions (0)
No revisions yet.