Änderung an Auswahl Sortieren. Theoretisch scheint korrekt zu sein, gibt aber keine Ergebnisse

Question

Ich lerne Ruby und die Art und Weise, wie ich das mache, ist durch das Lernen und Implementieren von Sortieralgorithmen. Während Auswahl Art arbeiten, habe ich versucht, es wie folgt zu ändern:

• In jedem Durchgang, anstatt die kleinste zu finden und es an die Spitze oder Anfang des Arrays zu bewegen, finden die kleinste und die größte und Bewegung sie an beiden Enden

• Für jeden durch~~POS=TRUNC, die Anfang inkrementieren und die Endpositionen der Anordnung zu verringern, die durch

• geschleift werden muß Während Swapping, wenn der identifizierte min und max in Positionen sind, die ausgelagert erhalten Miteinander, mach den Swap einmal (sonst werden zwei Swaps gemacht, 1 für den min und 1 für die max)

Dies scheint nicht in allen Fällen zu funktionieren. Fehle ich etwas in der Logik? Wenn die Logik stimmt, werde ich meine Implementierung noch einmal überprüfen, aber im Moment konnte ich nicht herausfinden, was falsch ist.

Bitte helfen.

Update: Dies ist mein Code für die Methode, um diese Art zu tun:

def mss(array) 
    start = 0; 
    stop = array.length - 1; 
    num_of_pass = 0 
    num_of_swap = 0 
    while (start <= stop) do 
    num_of_pass += 1 
    min_val = array[start] 
    max_val = array[stop] 
    min_pos = start 
    max_pos = stop 
    (start..stop).each do 
     |i| 
     if (min_val > array[i]) 
     min_pos = i 
     min_val = array[i] 
     end 
     if (max_val < array[i]) 
     max_pos = i 
     max_val = array[i] 
     end 
    end 
    if (min_pos > start) 
     array[start], array[min_pos] = array[min_pos], array[start] 
     num_of_swap += 1 
    end 
    if ((max_pos < stop) && (max_pos != start)) 
     array[stop], array[max_pos] = array[max_pos], array[stop] 
     num_of_swap += 1 
    end 
    start += 1 
    stop -= 1 
    end 
    puts "length of array = #{array.length}" 
    puts "Number of passes = #{num_of_pass}" 
    puts "Number of swaps = #{num_of_swap}" 
    return array 
end 

Answer 1

Das Problem kann

7 5 4 2 6 

Nach Durchsuchen der Array zum ersten Mal mit diesem Eingabearray gezeigt wird, haben wir

start = 0 
stop = 4 
min_pos = 3 
min_val = 2 
max_pos = 0 note: max_pos == start 
max_val = 7 

die erste if Anweisung wird dietauschenund 7, wird das Array zu

2 5 4 7 6 

Die zweite if Anweisung ändert nicht die 7 weil max_pos == start bewegen. Als Ergebnis bleibt die 6 am Ende des Arrays, was nicht das ist, was Sie wollen.