Lidt om algoritmen:
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.
Eksempel:
Sourcekode til eksempel:
SortAlgorithm.java
MyQuickSort.java
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.