Forskellen mellem quick sort og merge sort er at ved quick sort deles listen på en sådan måde
at alle elementerne i den første under liste er mindre end alle elementerne i den anden under
liste. De to under lister bliver så sorteret som i merge sort, men på grund af den tidligere
beskrevede betingelse er den sidste merge ikke nødvendig.
Listen deles ved at vælge en af elementerne og bruge den som en pivot. Hvis listen består
af tilfældige til, kan det første element i listen bruges som pivot. Det idelle ville være
at pivoten skal have en værdi der deler listen i to lige store dele.
Når pivoten er blevet valgt, bruges den til at sortere resten af listen i to under lister:
En hvor alle elementerne er mindre end pivoten, og en anden hvor alle elementerne er større
end pivoten. Disse to under lister bliver så sorteret rekursivt efter samme algoritme.
Den endelige sorterede liste fåes så ved at samle den første underliste, pivoten og den anden
under liste.
Hastighed.
Quick sort bruger ca. dobbelt så mange assignments som sammenligninger.
Ved sortering af usorterede lister er quick sort tilnærmelsesvis en O(n log n) algoritme.
Den bruger omkring O(n log n) sammenligninger og O(1.8n log n) assignments.
Hvis quick sort køres på en allerede sorteret liste er den nærmere en O(n2)
algoritme.
Eksemplet er implementeret på et array.
MyQuickSort.java indeholder metoden sort( int[] a ), som blot starter sorteringen med
kaldet til sort( int[] a, int lo, int hi ).
Det første metoden gør er at checke om array længden er kortere end et element. Hvis det er
tilfældet returnerer metoden. Herefter checkes efter om listen her en længde på netop 2
elementer. Der swappes hvis nødvendigt, hvorefter der returneres.
Hvis ingen af de to foregående kriterier er opfyldt fortsætter metoden med at oprette en ny
pivot, og flytte den til sidste element i det angivne array.
Herefter søges fremad fra a[lo] til der findes et element der er større end pivoten, eller
slutningen på arrayet nåes. Bagefter søges der bagud til der findes et element, der er
mindre end pivoten, eller starten på arrayet nåes. Der foretages herefter eventuelle ombytninger.
Til sidst kaldes metoden sort( int[] a, int lo, int hi ) rekursivt indtil arraystørrelserne
er på 2.
snakebyte.dk
