Algoritem za urejanje s porazdelitvami

Algoritem za urejanje s porazdelitvami (angl. Quicksort), včasih tudi algoritem za urejanje z izboljšanimi zamenjavami, je algoritem za urejanje, ki deluje po metodi deli in vladaj in se ga ponavadi implementira z uporabo rekurzije.

Deluje tako, da tabelo S razdelimo na dva dela S₁ in S₂, za katera velja, da so vsi elementi iz S₁ manjši od elementa x in vsi iz S₂ večji od vnaprej izbrane vrednosti x, ki jo imenujemo pivot. Ko izberemo pivot, se sprehajamo po tabeli najprej z leve in nato z desne, in ob tem iščemo elemente, ki niso na pravi strani. Ko naletimo na tak element na levi in na desni strani, ju preprosto zamenjamo in nadaljujemo sprehod. Ko se indeksa z leve in desne srečata sprehod zaključimo in rekurzivno postopek ponovimo na obeh tabelah S₁ in S₂ posebej. To ponavljamo, dokler ne pridemo do tabel dolžine 1, takrat pa je celotna tabela urejena.

Postopek delovanja

1. izberemo poljubni element tabele x (npr. srednji)
2. pregledujemo tabelo od leve proti desni, dokler ne najdemo a[i] > x
3. pregledujemo tabelo od desne proti levi, dokler ne najdemo a[j] < x
4. zamenjamo a[i] in a[j]
5. ponavljamo korake 2 – 4, dokler se pregledovanji ne srečata
6. postopek rekurzivno ponavljamo na levem in desnem delu tabele

Iterativni postopek

• izdelamo seznam zahtev po porazdelitvah, ki še niso bile opravljene
• vsakič nastaneta 2 zahtevi:

• eno (levo) obdelamo takoj,
• drugo (desno) umestimo na seznam

• zahtevke obravnavamo v obratnem vrstnem redu: utripajoč sklad

Psevdokoda algoritma

i

indeks levega elementa

j

indeks desnega elementa, gledano z desne

Spremenljivko j torej na začetku nastavimo na n, i pa na prvi element (0 ali 1, odvisno od označevanja). Recimo, da imamo tabelo S z n elementi:

dokler (n>i+j)           /* dokler se indeksa ne prekrižata */
 dokler (S[i] < a)       /* dokler mora biti S[i] na levi strani, i pomaknemo desno */
  i++
 dokler (S[j] > a)       /* dokler mora biti S[j] na desni strani, j pomaknemo levo */
  j--
 če je (i<=j)
  zamenjaj(S[i],S[j])
  i++
  j--

Lahko se zgodi, da S razpade tudi na S₁ a S₂. Tak primer je recimo tabela z elementi 5,5,5,5,5.

Primeri delovanja

Primer 1

44 55 12 42 94 6  18 67
         ** 
vzamemo srednji element
i
z i od začetka iščemo elemente, ki so večji od srednjega
                     j
z j od konca iščemo elemente, ki so manjši od srednjega

18 55 12 42 94 6  44 67
^^                ^^
    i          j

18  6 12 42 94 55 44 67
    ^          ^^
       i     j
         ij

18  6 12 42 94 55 44 67
       j     i
┌───────┬──┬──────────┐──imamo 3 dele tabele
│a[k]<x │  │  a[k]>x  │
       a[k]=x      

Sedaj postopek ponavljamo rekurzivno na vsakem delu tabele posebej.

Primer 2

Primer - worst case scenario

Poiščimo najslabši možni primer, ko se quicksort obnaša kot bubblesort:

a b c d e  sort(a,0,4) -> c=5
    5
   i j
       |5
a b e d|5  sort(a,0,3) -> b=4
  4
 i j
     |4 5
a d e|4 5  sort(a,0,2) -> d=3
  3
 i j
   |3 4 5
a e|3 4 5  sort(a,0,1) -> a=2
e|2 3 4 5
            e=1

Ko vstavimo na mesta števila dobimo najslabši primer:

2 4 5 3 1

Do takih primerov prihaja pri realni uporabi zelo poredko.

Časovna zahtevnost

Ker se lahko zgodi, da za a izberemo najmanjši ali največji element, in če imamo smolo ter se nam to dogaja skozi vso tabelo, postane urejanje s porazdelitvami časovne zahtevnosti Θ(n²). Prav tako je časovna zahtevnost na že sortirani tabeli Θ(n²). V povprečju pa je zahtevnost tega urejanja

Ker je ta algoritem rekurziven, porabi tudi najmanj O(log n) pa vse do O(n²) prostora na skladu, kar je včasih nezaželeno. Delno zato delno pa zaradi največje časovne zahtevnosti Θ(n²) se namesto quicksort algoritma marsikje uporablja urejanje s kopico.

k-ti najmanjši element

Ker quicksort razdeli tabelo na dva dela, bo v primeru, da je stevilo elementov v S₁ vecje ali enako k, k-to najmanjse stevilo zagotovo med njimi. Drugace pa bo v S₂.

Časovna zahtevnost

Pregledati moramo n, n/2, n/4, ..., kar znaša n(1+1/2+1/4+1/8+...) = 2*n

Tako kot pri sortiranju se tudi tu lahko zgodi, da pride do časovne zahtevnosti O(n²).

Analiza časovne kompleksnosti

• ena porazdelitev: O(n)
• število rekurzivnih klicev:

• ugoden (povprečen) primer: O(log2 n)
• najslabši primer: O(n)

• Skupaj: Ta = O(n*log2 n), vendar Tw = O(n2)

Izvajanje algoritma, po korakih konstanta narašča

...

Algoritem v Javi

Rekurzivni algoritem

public static void quicksort(Element[] a)
{
  System.out.println("Quick(0,"+(a.length-1)+")"); 
  a[0].izpisiTabelo(a);      
  sort(a,0,a.length-1);
}

public static void sort(Element[] a, int l, int r)
{
  int i=l, j=r;
  Element x=a[(l+r)/2], w;
 
  do
  {
    while (a[i].manjsi(x)) ++i;
    while (x.manjsi(a[j])) --j;
    if (i<=j)
    {
      w=a[i]; a[i]=a[j]; a[j]=w;
      ++i;
      --j;
    }
  } while (i<=j);
  if (l<j) 
  {
    System.out.println("LeftQuick("+l+","+j+")"); 
    a[0].izpisiTabelo(a);      
    sort(a,l,j);
  }
 
  if (i<r) 
  {
    System.out.println("RightQuick("+i+","+r+")"); 
    a[0].izpisiTabelo(a);      
    sort(a,i,r);
  }
 
}

Iterativni algoritem

private static class ElementSklada
{
	int l,r;
 
	ElementSklada(int l, int r)
	{
         this.l=l;
         this.r=r;
      }
}

public static void quicksortI(Element[] a)
{
  final int M = 50; 
  ElementSklada[] sklad = new ElementSklada[M];
  int i,l,j,r,s;
  Element x, w;
 
  s=0;
  sklad[0]=new ElementSklada(0,a.length-1);
  int vrh=1;
 
  System.out.println("Na sklad(0,"+(a.length-1)+")"); 
   a[0].izpisiTabelo(a);  
 
  do // dokler je kaj na skladu
  {    
    r=sklad[s].r;
    l=sklad[s].l;
    s--;
     System.out.println("S sklada("+l+","+r+")");  
    do
    {
      i=l;
      j=r;
      x=a[(l+r)/2];
      System.out.println("Indeks srednjega elementa = "+((l+r)/2)); 
 
      do
      { 
        while (a[i].manjsi(x)) {++i;}
        while (x.manjsi(a[j])) {--j;}
        if (i<=j)
        {
          w=a[i]; a[i]=a[j]; a[j]=w;
          ++i;
          --j;
        }
      } while (i<=j);
 
      a[0].izpisiTabelo(a);  
 
      if ((j-l)<(r-i))
      {
        if (i<r) 
        {
          System.out.println("Na sklad ("+i+","+r+")"); 
          s++;
          sklad[s]=new ElementSklada(i,r);    
        }
        r=j;
      }
      else
      {
        if (l<j) 
        {
          System.out.println("Na sklad ("+l+","+j+")"); 
          s++;
          sklad[s]=new ElementSklada(l,j);
        }
        l=i;
      }
    } while (l<=r);
  } while (s>=0); 
}

Povezave

• Opis, psevdokoda + Java simulacija
• Java simulacija (psevdokoda, tabela) (Quick Sort)
• The Animator
• xSortLab Applet
• Angleška wikipedia: Quicksort
• Java simulacija