HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Stability of QuickSort Algorithm

Submitted by: @import:stackexchange-cs··
0
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:

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.

Context

StackExchange Computer Science Q#144424, answer score: 9

Revisions (0)

No revisions yet.