QuickSort

Naredili bomo rekurzivni algoritem za urejanje polja. Najprej določimo indeks elementa , ki je na sredini polja je na sredini polja (x = polje[l+r], kjer l pomeni indeks levega dela (na začetku je 0), r pa pomeni indeks desnega dela (na začetku je n)). Vsi elementi, ki imajo indeks manjši od indeksa sredinskega elementa, morajo biti manjši od sredinskega elementa. Vsi elementi, ki imajo indeks večji od indeksa sredinskega elementa pa morajo biti večji od sredinskega elementa. Ko temu kriteriju zadostimo, kličemo funkcijo rekurzivno, tako da na isti način sortiramo še elemente na levi strani od sredinskega elementa (Quick(l, j)) in elemente na desni strani od sredinskega elementa (Quick(i,r)).

void QuickSort(int Polje[], int m, int n)
{

  int i, j; 
  if (m < n)
  { 
    i = m; j = n;

    Delitev(Polje,i,j);
    QuickSort(Polje,m,j);

    QuickSort(Polje,i,n); 
  }
} 

main()
{
  const int n=16;

  int polje[n]={44,55,12,42,94,6,18,67,3,13,99,15,23,77,59,17};

  Izpisi(polje, n);
  QuickSort(polje,0,n);

  Izpisi(polje,n);
  
  return 0;
}

void Delitev (int Polje[], int& i, int& j) 
{ 
       int Srednji, Temp; 
       Srednji = Polje[ (i + j) / 2 ] ; 
       do { 
               while (Polje[i] < Srednji) i++; 
               while (Polje[j] > Srednji) j--; 
               if (i <= j) {

                  Temp = Polje[i];     
                  Polje[i] = Polje[j];         
                  Polje[j] = Temp;

                   i++; j--;
               }
       } while (i <= j);
} 

Primer izpisa:

Začetno polje:
44, 55, 12, 42, 94,  6, 18, 67,  3, 13, 99, 15, 23, 77, 59, 17,

Program izvaja naslednje zamenjave:

 3, 55, 12, 42, 94,  6, 18, 67, 44, 13, 99, 15, 23, 77, 59, 17, 

 3, 17, 12, 42, 94,  6, 18, 67, 44, 13, 99, 15, 23, 77, 59, 55, 

 3, 17, 12, 42, 23,  6, 18, 67, 44, 13, 99, 15, 94, 77, 59, 55, 

 3, 17, 12, 42, 23,  6, 18, 15, 44, 13, 99, 67, 94, 77, 59, 55, 

 3, 17, 12, 42, 23,  6, 18, 15, 13, 44, 99, 67, 94, 77, 59, 55, 

 3, 17, 12, 13, 23,  6, 18, 15, 42, 44, 99, 67, 94, 77, 59, 55, 

 3, 17, 12, 13, 15,  6, 18, 23, 42, 44, 99, 67, 94, 77, 59, 55, 

 3,  6, 12, 13, 15, 17, 18, 23, 42, 44, 99, 67, 94, 77, 59, 55, 

 3,  6, 12, 13, 15, 17, 18, 23, 42, 44, 55, 67, 94, 77, 59, 99, 

 3,  6, 12, 13, 15, 17, 18, 23, 42, 44, 55, 67, 59, 77, 94, 99, 

 3,  6, 12, 13, 15, 17, 18, 23, 42, 44, 55, 59, 67, 77, 94, 99, 

Končna razvrstitev je naslednja:

3, 6, 12, 13, 15, 17, 18, 23, 42, 44, 55, 59, 67, 77, 94, 99,