Blasensortierung durchführen und mit Ruby sortieren auswählen

Zweck

Schreiben wir den Code und fassen den Sortieralgorithmus zusammen. Ich werde die Sprache in Ruby ausprobieren.

Über das Sortieren

Durch Sortieren werden die als Eingabe angegebenen Zahlen in aufsteigender Reihenfolge sortiert.

Blasensorte

Die Blasensortierung wiederholt den Vorgang des "Vergleichens und Austauschs zweier benachbarter Zahlen von rechts nach links in einer Folge von Zahlen". Wenn der Vorgang für eine Zahlenfolge einmal ausgeführt wird, befindet sich die kleinste Zahl im ersten Teil des Arrays. Es kann sortiert werden, indem die Anzahl der Elemente umgangen wird.

bubble.rb

def bubble_sort(array)
  length = array.length
  (length - 1).times do |round|
    (length - 1 - round).times do |n|
      if array[length - n - 1] < array[length - n - 2]
        smaller = array[length - n - 1]
        array[length - n - 1] = array[length - n - 2]
        array[length - n - 2] = smaller
      end
    end
  end
  array
end

array = [2, 3, 13, 7, 8, 9, 11, 1, 5]
bubble_sort(array)　#=> [1, 2, 3, 5, 7, 8, 9, 11, 13]

Inhalt der Blasensortierfunktion

• Ermittelt die Länge des Array-Arrays als Länge (1. Zeile) ・ (Länge -1) Der Austausch erfolgt in der Runde (2. Zeile) ・ Vergleichen Sie in der n-ten Runde (Länge --n - 1) mal und ersetzen Sie (3. Zeile) ・ Wenn der Wert links größer als der Wert rechts ist, ersetzen Sie ihn (Zeilen 4 bis 7). Die Anzahl der Größenvergleiche beträgt (Länge -1) + (Länge -2) + ・ ・ ・ + 1 = (Länge) ^ 2/2.

Selektive Sortierung

Die Auswahlsortierung wiederholt den Vorgang "Suchen nach dem Mindestwert in der Zahlenspalte und Ersetzen durch die Zahl ganz links".

selection.rb

def selection_sort(array)
  length = array.length
  (length - 1).times do |round|
    min = round + 1
    round.upto(length - 1) do |n|
      if array[n] < array[min]
        min = n
      end
    end
    min_number = array[min]
    array[min] = array[round]
    array[round] = min_number
  end
  array
end

Holen Sie sich die minimale Indexnummer, suchen Sie danach und ersetzen Sie sie. Wie bei der Blasensortierung beträgt die Anzahl der Größenvergleiche (Länge) ^ 2/2.

Nachtrag

Als nächstes fasse ich die Einfügesortierung, die Heap-Sortierung, die Zusammenführungssortierung, die schnelle Sortierung und die Bucket-Sortierung zusammen.