Quicksort Drama

Question

Ich konnte nur meinen Kopf gegen die Wand schlagen. Ich verstehe nicht, warum mein folgender Quicksort-Algorithmus nicht funktioniert. Es wird in Pascal geschrieben:

program quicksort; 

Type iArray = array [0..8] of integer; 
var intArray, newArray : iArray; 

Function getIntArray(localIntArray : iArray) : iArray; 
begin 
    localIntArray[0] := 3; 
    localIntArray[1] := 1; 
    localIntArray[2] := 8; 
    localIntArray[3] := 4; 
    localIntArray[4] := 9; 
    localIntArray[5] := 0; 
    localIntArray[6] := 8; 
    localIntArray[7] := 2; 
    localIntArray[8] := 5; 
    getIntArray := localIntArray; 
end; 

Procedure writeArray(localIntArray : iArray); 
var i:integer; 
begin 
    for i:=low(localIntArray) to high(localIntArray) do begin 
     write(localIntArray[i]); 
    end; 
    writeln(''); 
end; 

Procedure quicksort(links : integer ; rechts:integer; localIntArray : iArray); 
// links:  Index des 1. Elements, rechts: Index des letzten Elements 
var l, r, pivot, pivotValue, temp : Integer; 


    Function swap (larray : iArray; links :integer; rechts:integer) : iArray;         
    // Ich tausche in einem IntegerArray die Positionen links und rechts 
    var temp : integer; 
    begin 
     temp     := larray[links]; 
     larray[links]   := larray[rechts]; 
     larray[rechts]   := temp; 
     swap     := larray; 
    end; 

begin 
    if (rechts>links) then begin 
    l:= links; 
    r:= rechts; 
    pivot := localIntArray[(rechts+links) div 2]; 

    while (l<r) do begin 
     while localIntArray[l] < pivot do l:=l+1; 
     while localIntArray[r] > pivot do r:=r-1; 
     if (l<=r) then begin 
     localIntArray := swap(localIntArray,l,r); 
     l := l+1; 
     r := r-1; 
     end; 
    end; 

    if (links < r) then quicksort(links, r, localIntArray); 
    if (rechts > l) then quicksort(l, rechts, localIntArray); 

    writeln('s Array: '); 
    writeArray(localIntArray); 
    end; 
end; 

var i : integer; 
begin 

    intArray := getIntArray(intArray); 
    writeln('Unsortiertes Array: '); 
    writeArray(intArray); 
    quicksort(low(intArray), high(intArray), intArray); 

end. 

Wenn ich Eingabe der Array: 3,1,8,4,9,0,8,2,5 ich die folgenden Berechnungen erhalten:

0,1,2,3,5,4,8,8,9 ->0,1,2,3,5,4,8,8,9 ->3,1,2,0,4,5,8,8,9 ->3,1,2,0,4,5,8,8,9 ->3,1,2,0,4,5,8,8,9 ->3,1,2,0,5,4,8,8,9 ->3,1,8,4,5,0,8,2,9

Was passiert hier?

Answer 1

Ihr Programm schlägt fehl, weil Sie mit Kopien des Arrays arbeiten, anstatt direkt zu arbeiten. So betrachtet die Deklaration von quicksort:

Procedure quicksort(links, rechts: integer; localIntArray: iArray); 

Das Array wird als Wert übergeben. Sie übergeben das Array an die Prozedur, aber alle Änderungen am Array werden vom Aufrufer nie gesehen. Stattdessen müssen Sie an Ort und Stelle arbeiten, indem Sie einen Verweis auf das Array übergeben. Das ist ein var Parameter:

Procedure quicksort(links, rechts: integer; var localIntArray: iArray); 

Und Sie müssen ebenfalls mit dem swap Verfahren zu tun, die wie folgt erklärt werden sollen:

Procedure swap(var larray: iArray; links, rechts: integer); 

Hier ist ein komplettes Programm, das korrekt sortiert:

program quicksort24335585; 

Type 
    iArray = array [0 .. 8] of integer; 

var 
    intArray: iArray; 

Function getIntArray(localIntArray: iArray): iArray; 
begin 
    localIntArray[0] := 3; 
    localIntArray[1] := 1; 
    localIntArray[2] := 8; 
    localIntArray[3] := 4; 
    localIntArray[4] := 7; 
    localIntArray[5] := 0; 
    localIntArray[6] := 8; 
    localIntArray[7] := 2; 
    localIntArray[8] := 5; 
    getIntArray := localIntArray; 
end; 

Procedure writeArray(localIntArray: iArray); 
var 
    i: integer; 
begin 
    for i := low(localIntArray) to high(localIntArray) do 
    begin 
    write(localIntArray[i], ' '); 
    end; 
    writeln(''); 
end; 

Procedure quicksort(links: integer; rechts: integer; var localIntArray: iArray); 
// links:  Index des 1. Elements, rechts: Index des letzten Elements 
var 
    l, r, pivot: integer; 

    procedure swap(var larray: iArray; links: integer; rechts: integer); 
    // Ich tausche in einem IntegerArray die Positionen links und rechts 
    var 
    temp: integer; 
    begin 
    temp := larray[links]; 
    larray[links] := larray[rechts]; 
    larray[rechts] := temp; 
    end; 

begin 
    if (rechts > links) then 
    begin 
    l := links; 
    r := rechts; 
    pivot := localIntArray[(rechts + links) div 2]; 

    while (l < r) do 
    begin 
     while localIntArray[l] < pivot do 
     l := l + 1; 
     while localIntArray[r] > pivot do 
     r := r - 1; 
     if (l <= r) then 
     begin 
     swap(localIntArray, l, r); 
     l := l + 1; 
     r := r - 1; 
     end; 
    end; 

    if (links < r) then 
     quicksort(links, r, localIntArray); 
    if (rechts > l) then 
     quicksort(l, rechts, localIntArray); 
    end; 
end; 

begin 
    intArray := getIntArray(intArray); 
    writeln('Unsortiertes Array: '); 
    writeArray(intArray); 

    quicksort(low(intArray), high(intArray), intArray); 

    writeln('s Array: '); 
    writeArray(intArray); 

    Readln; 
end. 

Ausgabe

 
Unsortiertes Array: 
3 1 8 4 7 0 8 2 5 
s Array: 
0 1 2 3 4 5 7 8 8 

Ich bin mir ziemlich sicher, dass das Programm poliert und verbessert werden konnte. Dies wird Teil Ihrer Lernkurve sein!