Clasificación rápida estable

Se dice que un algoritmo de clasificación es estable si mantiene el orden relativo de los registros en el caso de igualdad de claves.
 

Entrada: (1, 5), (3, 2) (1, 2) (5, 4) (6, 4) 
Necesitamos ordenar los pares clave-valor en el orden creciente de las claves del primer dígito 
Hay dos soluciones posibles para los dos pares donde la clave es la misma, es decir (1, 5) y (1, 2) como se muestra a continuación: 
SALIDA1: (1, 5), (1, 2), (3, 2), (5, 4) , (6, 4) 
SALIDA2: (1, 2), (1, 5), (3, 2), (5, 4), (6, 4) 
Un algoritmo estable produce la primera salida. Puede ver que (1, 5) viene antes que (1, 2) en el orden ordenado, que era el orden original, es decir, en la entrada dada, (1, 5) viene antes que (1, 2).
La segunda salida solo puede ser producida por un algoritmo inestable. Puede ver que en la segunda salida, (1, 2) viene antes de (1, 5), lo cual no era el caso en la entrada original.

Algunos algoritmos de clasificación son estables por naturaleza, como la clasificación por inserción , la clasificación por fusión, la clasificación por burbuja , etc. Y algunos algoritmos de clasificación no lo son, como la clasificación en montón, la clasificación rápida , etc.  La clasificación rápida
es un algoritmo inestable porque intercambiamos elementos de acuerdo con la posición del pivote. (sin considerar sus posiciones originales).
¿Cómo hacer que QuickSort sea estable?
 

Quicksort puede ser estable, pero normalmente no se implementa de esa manera. Hacerlo estable requiere almacenamiento de orden N (como en una implementación ingenua) o un poco de lógica adicional para una versión en el lugar. 
En la implementación a continuación, usamos espacio adicional. La idea es hacer dos listas separadas: 
1) La primera lista contiene elementos más pequeños que el pivote. 
2) La segunda lista contiene elementos mayores que el pivote.
 

// C++ code to implement Stable QuickSort.
// The code uses middle element as pivot.
#include <bits/stdc++.h>
using namespace std;
 
    vector<int> quickSort(vector<int> ar)
    {
     
        // Base case
        if(ar.size() <= 1)
        {
            return ar;
        }
        else
        {
         
            // Let us choose middle element a pivot           
            int mid = ar.size() / 2;
            int pivat = ar[mid];
             
        // key element is used to break the array
            // into 2 halves according to their values
            vector<int> smaller ;
            vector<int> greater ;
             
            // Put greater elements in greater list,
        // smaller elements in smaller list. Also,
        // compare positions to decide where to put.       
        for(int ind = 0; ind < ar.size(); ind++)
        {
            int val = ar[ind];
            if( ind != mid )
            {
                if( val < pivat )
                {
                    smaller.push_back(val);
                }
                else if(val > pivat)
                {
                    greater.push_back(val);
                }
                else
                {
                     
                    // If value is same, then considering
                    // position to decide the list.               
                    if(ind < mid)
                    {
                        smaller.push_back(val);
                    }
                    else
                    {
                        greater.push_back(val);
                    }
                }
            }
        }
             
        vector<int> ans;           
        vector<int> sa1 = quickSort(smaller);
        vector<int> sa2 = quickSort(greater);
             
        // add all elements of smaller list into ans list
        for(int val1 : sa1)
                ans.push_back(val1);
                 
        // add pivat element into ans list
        ans.push_back(pivat);
             
        // add all elements of greater list into ans list
        for(int val2 : sa2)
                ans.push_back(val2);
             
        // return ans list
        return ans;       
        }
    }
     
    // Driver code
    int main()
    {   
        int ar[] = {10, 7, 8, 9, 1, 5};
        vector<int> al;
        al.push_back(10);
        al.push_back(7);
        al.push_back(8);
        al.push_back(9);
        al.push_back(1);
        al.push_back(5);   
        vector<int> sortedAr = quickSort(al);
         
        for(int x:sortedAr)
        cout<<x<<" ";
    }
 
// This code is contributed by Pushpesh Raj

// Java code to implement Stable QuickSort.
// The code uses middle element as pivot.
import java.util.*;
class GFG
{
    public static ArrayList<Integer> quickSort(ArrayList<Integer> ar)
    {
       
        // Base case
        if(ar.size() <= 1)
        {
            return ar;
        }
        else
        {
           
            // Let us choose middle element a pivot            
            int mid = ar.size() / 2;
            int pivat = ar.get(mid);
             
           // key element is used to break the array
            // into 2 halves according to their values
            ArrayList<Integer> smaller = new ArrayList<>();
            ArrayList<Integer> greater = new ArrayList<>();
             
            // Put greater elements in greater list,
           // smaller elements in smaller list. Also,
           // compare positions to decide where to put.        
           for(int ind = 0; ind < ar.size(); ind++)
           {
               int val = ar.get(ind);
               if( ind != mid )
               {
                   if( val < pivat )
                   {
                       smaller.add(val);
                   }
                   else if(val > pivat)
                   {
                       greater.add(val);
                   }
                   else
                   {
                      
                       // If value is same, then considering
                       // position to decide the list.                   
                       if(ind < mid)
                       {
                           smaller.add(val);
                       }
                       else
                       {
                           greater.add(val);
                       }
                   }
               }
           }
            
           ArrayList<Integer> ans = new ArrayList<Integer>();              
           ArrayList<Integer> sa1 = quickSort(smaller);
           ArrayList<Integer> sa2 = quickSort(greater);
            
           // add all elements of smaller list into ans list
           for(Integer val1 : sa1)
                ans.add(val1);
                 
           // add pivat element into ans list   
           ans.add(pivat);
            
           // add all elements of greater list into ans list
           for(Integer val2 : sa2)
                ans.add(val2);
            
           // return ans list
           return ans;        
        }
    }
     
    // Driver code 
    public static void main(String args[])
    {      
        int ar[] = {10, 7, 8, 9, 1, 5};
        ArrayList<Integer> al = new ArrayList<>();
        al.add(10);
        al.add(7);
        al.add(8);
        al.add(9);
        al.add(1);
        al.add(5);       
        ArrayList<Integer> sortedAr = quickSort(al);
        System.out.println(sortedAr);
    }
}
 
// This code is contributed by Naresh Saharan

# Python code to implement Stable QuickSort.
# The code uses middle element as pivot.
def quickSort(ar):
      
    # Base case
    if len(ar) <= 1:
        return ar
 
    # Let us choose middle element a pivot
    else:
        mid = len(ar)//2
        pivot = ar[mid]
 
        # key element is used to break the array
        # into 2 halves according to their values
        smaller,greater = [],[]
  
        # Put greater elements in greater list,
        # smaller elements in smaller list. Also,
        # compare positions to decide where to put.
        for indx, val in enumerate(ar):
            if indx != mid:
                if val < pivot:
                    smaller.append(val)
                elif val > pivot:
                    greater.append(val)
 
                # If value is same, then considering
                # position to decide the list.
                else:
                    if indx < mid:
                        smaller.append(val)
                    else:
                        greater.append(val)
        return quickSort(smaller)+[pivot]+quickSort(greater)
     
# Driver code to test above
ar = [10, 7, 8, 9, 1, 5]
sortedAr = quickSort(ar)
print(sortedAr)

[1, 5, 7, 8, 9, 10]

En el código anterior, hemos usado intencionalmente el elemento central como pivote para demostrar cómo considerar la posición como parte de la comparación. El código se simplifica mucho si usamos el último elemento como pivote. En el caso del último elemento, siempre podemos empujar elementos iguales en la lista más pequeña.