Thema indholdsfortegnelse -- Tastaturgenvej: 'u'  Forrige tema i denne lektion -- Tastaturgenvej: 'p'  Næste slide i denne lektion -- Tastaturgenvej: 'n'Rekursion
37.  Quicksort

Som det sidste indslag i lektionen om rekursion ser vi her på Quicksort. Quicksort sorterer et array, ligesom det var tilfældet med Bubblesort i afsnit 24.4.

Quicksort er en klassisk rekursiv sorteringsprocedure. Tilmed er Quicksort bredt anerkendt som én af de bedste sorteringsteknikker overhovedet.

Hvis man skal bruge Quicksort i C skal man anvende qsort fra standard C biblioteket. Programmet, som udvikles i denne lektion er funktionel, men ikke optimal i praktisk forstand. Det er svært at programmere Quicksort med henblik på god, praktisk anvendelighed.

37.1 Quicksort (1)37.3 Quicksort (3)
37.2 Quicksort (2)37.4 Quicksort (4)
 

37.1.  Quicksort (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I dette afsnit vil vi med ord beskrive den algoritmiske idé i Quicksort. I afsnit 37.2 viser vi den overordnede rekursive sorteringsfunktion i C. I afsnit 37.3 diskuterer vi den centrale detalje i algoritmen, som er en iterativ array opdelningsfunktion. Endelig, i afsnit 37.4 vurderer vi god Quicksort er i forhold til Bubblesort.

Quicksort er et eksempel på en rekursiv sorteringsteknik der typisk er meget mere effektiv end f.eks. boblesortering

  • Algoritmisk idé:

    • Udvælg et vilkårligt deleelement blandt tabellens elementer

    • Reorganiser tabellen således at den består af to dele:

      • En venstre del hvor alle elementer er mindre end eller lig med deleelementet

      • En højre del hvor alle elementer er større end eller lig med deleelementet

    • Sorter både venstre og højre del af tabellen rekursivt, efter samme idé som netop beskrevet

Reorganiseringen af elementerne i punkt to herover kan opfattes som en grovsortering af tabellen i små og store elementer, relativ til deleelementet.

Quicksort er et andet eksempel på en rekursiv del og hersk løsning

En stor del af arbejdet består i opdelning af problemet i to mindre delproblemer, som egner sig til en rekursiv løsning

Sammensætningen af delproblemernes løsninger er triviel

 

37.2.  Quicksort (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Herunder viser vi C funktionen quicksort. Som det ses er der to rekursive kald quicksort i hver aktivering af quicksort. Baseret på vores erfaring med Fibonacci tal fra afsnit 34.2 og Towers of Hanoi fra afsnit 36.2 kunne det godt få alarmklokkerne til at ringe med tonerne af 'langsommelighed'. Det viser sig dog at være ubegrundet. Mere om dette i afsnit 37.4.

1
2
3
4
5
6
7
8
9
10
11
/* Sort the array interval a[from..to] */
void quicksort(element a[], index from, index to){
  index point1, point2;

  if (from < to){
    do_partitioning(a, from, to, &point1, &point2); 
    partitioning_info(a, from, to, point1, point2);
    quicksort(a, from, point1);
    quicksort(a, point2, to);
  }
}
Program 37.1    Den rekursive quicksort funktion.

Det er ligetil at forstå program 37.1 ud fra opskriften - den algoritmiske idé - i afsnit 37.1. Kaldet af do_partitioning udvælger dele elementet og foretager opdelningen af arrayet i en venstre del med små elementer og en højre del med store elementer. Med andre ord bestyrer do_partitioning grovsorteringen.

Givet en veludført opdelning kan sorteringsopgaven fuldføres ved at sortere de små elementer i den første røde del. Dernæst sorteres de store elementer i den anden røde del. Dette gøres naturligvis rekursivt, fordi denne opgave er af præcis samme natur som det oprindelige problem. Bemærk her, at når de to rekursive sorteringer er fuldført, er der ikke mere arbejdet at der skal udføres i den oprindelige sortering. Der er altså intet kombinationsarbejde, som vi ofte ser i forbindelse med del og hersk problemløsning.

 

37.3.  Quicksort (3)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi vil nu se på den centrale 'detalje' i quicksort, nemlig grovsorteringen. Dette udføres af et kald af do_partitioning, som vises i program 37.2.

Funktionen do_partitioning opdeler den del af arrayet a som er afgrænset af indekserne from og to. Resultatet af opdelningen er to indekser, der føres tilbage fra do_partitioning via to call by reference parametre point_left og point_right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* Do a partitioning of a, and return the partitioning
   points in *point_left and *point_right */
void do_partitioning(element a[], index from, index to,
                     index *point_left, index *point_right){
 index i,j;
 element partitioning_el;

 i = from - 1; j = to + 1;
 partitioning_el = a[from];
 do{
   do {i++;} while (a[i] < partitioning_el);  
   do {j--;} while (a[j] > partitioning_el);  
   if (i < j) swap(&a[i],&a[j]);
 } while (i < j); 

 if (i > j) {
   *point_left = j; *point_right = i;}
 else {
   *point_left = j-1; *point_right = i+1;}  
}
Program 37.2    Funktionen do_partitioning der opdeler tabellens elementer op i store og små.

Lad os løbe hen over do_partitioning i nogen detalje. På den tilknyttede slide findes der en billedserie, som støtter forståelsen af opdelningen. Den brune del udvælger et deleelement blandt tabellens elementer. Et hvilket som helst element kan vælges. Vi vælger blot a[from], altså det første. Indekserne i og j gennemløber nu tabellen fra hver sin side i den sorte while-løkke. i tvinges frem af den røde do-løkke, og j tvinges tilbage af den blå do-løkke. For hvert gennemløb af den ydre while-løkke foretages en ombytning af en uorden i tabellen. Den lilla del forneden sørger for justeringen af de endelige delepunkter.

Som man kan se er der en del detaljer at tage sig af i do_partitioning. Det er svært at tune disse, så man får en god, praktisk og velfungerende implementation af Quicksort ud af det.

 

37.4.  Quicksort (4)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I dette afsnit vil vi kort indse, at vores bekymring om køretiden fra afsnit 37.2 ikke er begrundet. Selv om Quicksort kalder sig selv to gange er vi meget langt fra at udføre et eksponentielt arbejde.

En god implementation plejer at være blandt de allerbedste sorteringsmetoder - men der er ingen garanti

  • Køretid i bedste tilfælde:

    • I størrelsesordenen n · log2 (n) sammenligninger og ombytninger.

  • Køretid i værste tilfælde

    • I størrelsesordenen n2 sammenligninger og ombytninger.

Argumentet for bedste tilfælde køretiden på n . log(n) er følgende. Hvert kald af do_partitioning har en køretid proportional med afstanden to - from. Hvis vi derfor kalder do_partitioning på et array af størrelsen n udfører vi et arbejde som svarer til n. Vi siger også undertiden at arbejdet er O(n).

Antag nu, at do_partitioning deler tabellen på midten i hvert rekursivt kald. Disse opdelninger kan foretages log(n) gange. Samlet set (over alle kald på et givet niveau) udføres et arbejde i do_partitioningn på hvert af de log(n) niveauer. Derfor er køretiden af Quicksort samlet set n . log(n).

Hvis do_partitioning skævdeler tabellen i 1 og (n-1) elementer opnås køretiden i værste tilfælde. Dermed får vi n niveauer hver med et samlet opdelningsarbejde på n. Med dette bliver køretiden af Quicksort på n . n.

n n2 n · log2 (n)
100 10.000 664
1000 1.000.000 9.966
10.000 100.000.000 132.887
100.000 10.000.000.000 1.660.964
Tabel 37.1    En tabel der illustrerer forskellen på væksten af n2 og n · log2 (n)

Det kan vises at en sortering med i størrelsesordenen n · log (n) sammenligninger og ombytninger er optimal.

Genereret: Onsdag 7. Juli 2010, 15:12:39
Thema indholdsfortegnelse -- Tastaturgenvej: 'u'  Forrige tema i denne lektion -- Tastaturgenvej: 'p'  Næste slide i denne lektion -- Tastaturgenvej: 'n'