4
$\begingroup$

Def: the stability of algorithm is defined in case of the algorithm preserves same value elements while sorting as the following shows:

enter image description here

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(i<=j){
            while(data[i]<pivot)
                i++;
            while(data[j]>pivot)
                j--;
            if(i<=j){
                int temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i++;
                j--;
            }
        }

        if(low<j)
            sort(data, low, j);
        if(high>i)
            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?

$\endgroup$
5
  • 2
    $\begingroup$ stable means, it maintains input order. If duplicate values are given as input, output will maintain given input order. Quick sort is not a stable algorithm because it swaps non-adjacent elements. $\endgroup$ Oct 2, 2021 at 18:37
  • $\begingroup$ @Md.FaisalHabib. Thank you. Why is not stable please? If make a split based on a pivot say 2, then in the second iteration we will $5'$ will be in the correct position and also $5$, so they won't be swapped based on algorithm posted above, what do you think please? $\endgroup$
    – Avv
    Oct 2, 2021 at 18:41
  • 3
    $\begingroup$ In QuickSort swapping of elements are done according to pivot's position (without considering their original positions). Please check stackoverflow.com/questions/13498213/… . Although you can make it stable by not implementing in the typical way. geeksforgeeks.org/stable-quicksort stackoverflow.com/questions/5804115/… $\endgroup$ Oct 2, 2021 at 18:56
  • $\begingroup$ @Md.FaisalHabib. It does not seem with above code it can be stable based on your comment. $\endgroup$
    – Avv
    Oct 2, 2021 at 19:11
  • $\begingroup$ Note that you can turn any sort into a stable sort by appending the original index as a secondary key. en.wikipedia.org/wiki/Schwartzian_transform $\endgroup$
    – Pseudonym
    Oct 27, 2021 at 8:03

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you. Appreciated. So, can you please tell if why the sorting algorithm posted is not stable for the same reason I mentioned in comment: If make a split based on a pivot say 2, then in the second iteration we will $5′$ will be in the correct position and also $5$, so they won't be swapped based on algorithm posted above, what do you think please? Also if we sorted it by name and then by year, if one is newer than the other, they will be swapped again unless they also occurred in the same year. $\endgroup$
    – Avv
    Oct 2, 2021 at 18:45
0
$\begingroup$

You can’t make Quicksort stable easily. Say you have an array with a million non-negative integers, and say five percent are zeroes. Quicksort will during the first partitioning move all zeroes from the second half to the first half, in reverse order, and that would be very hard to prevent.

As far as using a stable algorithm for sorting by multiple columns, I’d say sorting once with a more complex sorting criteria will be much more efficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.