Faire un tri à bulles et sélectionner le tri avec Ruby

Objectif

Écrivons en fait le code et résumons l'algorithme de tri. Je vais essayer la langue en Ruby.

À propos du tri

Le tri trie les nombres donnés en entrée dans l'ordre croissant.

Tri à bulles

Le tri par bulles répète l'opération de "comparaison et échange de deux nombres adjacents de droite à gauche dans une séquence de nombres". Si vous effectuez un cycle de traitement pour une séquence de nombres, le plus petit nombre sera dans le premier du tableau. Il peut être trié en faisant le tour du nombre d'éléments.

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]

Contenu de la fonction de tri à bulles -Obtenir la longueur du tableau en tant que longueur (1ère ligne) ・ (Longueur -1) Le remplacement est effectué au tour (2ème ligne) ・ Au nième tour, comparez (longueur --n --1) fois et remplacez (3e ligne) ・ Si la valeur de gauche est supérieure à la valeur de droite, remplacez-la (lignes 4 à 7). Le nombre de comparaisons de magnitude est (longueur -1) + (longueur -2) + ・ ・ ・ + 1 = (longueur) ^ 2/2.

Tri sélectif

Le tri de sélection répète l'opération de "recherche de la valeur minimale dans la colonne numérique et la remplaçant par le nombre le plus à gauche".

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

Obtenez le numéro d'index minimal, recherchez-le, puis remplacez-le. Identique au tri à bulles, le nombre de comparaisons de taille est de (longueur) ^ 2/2.

Postscript

Ensuite, je résumerai le tri par insertion, le tri par tas, le tri par fusion, le tri rapide et le tri par seau.