À l'aide de la méthode de tri à Bulles pour un tableau en Ruby

Je suis en train de mettre en œuvre la méthode de tri à Bulles dans un simple problème de codage pour le Rubis, mais je vais avoir quelques difficultés. Je comprends l'idée, c'est de regarder la valeur du premier élément et de le comparer à la valeur du deuxième élément et le swap en conséquence, mais je n'arrive pas à le faire dans un réel problème. Quelqu'un serait-il prêt à donner un bref exemple de la façon dont cela pourrait fonctionner en Ruby?

Avez-vous vraiment besoin de la bulle de tri? Est-il destiné à l'enseignement ou à des fins pratiques? Pour des raisons pratiques, Ruby a beaucoup de façons de tri qui renvoie les mêmes résultats. Par exemple, pour l'ascension de tri d'un tableau, vous pourriez faire: >> array.tri { |a, b| a <=> b }

OriginalL'auteur ppreyer | 2012-06-18

13

Mise en œuvre correcte du tri à bulles avec une boucle while
```
def bubble_sort(list)
  return list if list.size <= 1 # already sorted
  swapped = true
  while swapped do
    swapped = false
    0.upto(list.size-2) do |i|
      if list[i] > list[i+1]
        list[i], list[i+1] = list[i+1], list[i] # swap values
        swapped = true
      end
    end    
  end

  list
end
```
Veuillez expliquer pourquoi votre solution est "plus correct" (ne pas qu'il ne l'est pas, mais qu'il faut toujours expliquer pourquoi)...
Oui, mais pourquoi la réponse incorrecte si le bloc-échangé est définie à true... comment inverser le booléen changé l'exactitude de la déclaration de valeur. Dans ce cas, je dirais "c'est correcte, car le tri à bulles maintient le tri il y a encore de swaps - dès qu'il ne trouve pas plus de swaps, il s'arrête de tri"

OriginalL'auteur cluv

arr = [4,2,5,1]
loop until arr.each_cons(2).with_index.none?{|(x,y),i| arr[i],arr[i+1] = y,x if x > y}
p arr #=> [1, 2, 4, 5]

OriginalL'auteur steenslag

2

Source
```
def bubble_sort(list)
  return list if list.size <= 1 # already sorted

  loop do
    swapped = false
    0.upto(list.size-2) do |i|
      if list[i] > list[i+1]
        list[i], list[i+1] = list[i+1], list[i] # swap values
        swapped = true
      end
    end
    break unless swapped
  end

  list
end
```
Bien que je recommanderais certainement quelque chose à un meilleur moment de l'exécution que de bubblesort 🙂

Grâce VanDarg...je suis en suivant Chris Pine tutoriel et il n'a jamais compris quoi que ce soit sur les conditions de la boucle ou de la rupture, sauf. Est-il un autre moyen d'aller sur l'implémentation de ce code par exemple avec une boucle while?

OriginalL'auteur Chris Dargis

Voici ma version de la réponse sommet. Il appelle à la taille sur le tableau qu'une seule fois au lieu de chaque boucle. Il ne se compare pas les éléments une fois qu'ils ont déménagé à la fin du tableau.

Et la boucle while se ferme une boucle plus tôt. Vous avez terminé une fois que vous avez traversé l'ensemble de la baie et à seulement un swap, donc pas besoin de faire un autre avec 0 swaps.

def bubble_sort(list)
  iterations = list.size - 2

  return list unless iterations > 0 # already sorted

  swaps = 2

  while swaps > 1 do
    swaps = 0

    0.upto(iterations) do |i|
      if list[i] > list[i + 1]
        list[i], list[i + 1] = list[i + 1], list[i] # swap values
        swaps += 1
      end
    end

    iterations -= 1
  end

  list
end

L'exécution de ce test prend 25% de temps en moins.

that_array = this_array = [22,66,4,44,5,7,392,22,8,77,33,118,99,6,1,62,29,14,139,2]
49.times {|variable| that_array = that_array + this_array}
bubble_sort that_array

OriginalL'auteur calasyr

Viens de re-écrire @VanDarg du code pour utiliser une boucle while
(note: le code n'est pas testé... exécuter à vos risques et périls)

def bubble_sort(list)
  return list if list.size <= 1 # already sorted

  swapped = true
  while swapped
    swapped = false # maybe this time, we won't find a swap
    0.upto(list.size-2) do |i|
      if list[i] > list[i+1]
        list[i], list[i+1] = list[i+1], list[i] # swap values
        swapped = true # found a swap... keep going
      end
    end
  end

  list
end

Edit: mis à jour échangé-valeur en raison de tri à bulles maintient le tri il y a encore de swaps - dès qu'il ne trouve pas plus de swaps, il s'arrête de tri. Remarque, cela ne pas suivez @Doug code, mais ne sont conformes avec @cLuv fixer

OriginalL'auteur Taryn East

def bubble_sort array 
  array.each do
    swap_count = 0
    array.each_with_index do |a, index|
      break if index == (array.length - 1)
      if a > array[index+1]
        array[index],array[index+1] = array[index +1], array[index]
        swap_count += 1
      end
    end
    break if swap_count == 0 # this means it's ordered
  end
  array
end

Essayez de fournir plus de détails dans votre réponse.

OriginalL'auteur Basil

De la ligne droite avant:

def bubble_sort(n)
  return n if n.length <= 1

  0.upto(n.length - 1) do |t|
    0.upto(n.length - 2 - t) do |i|
      if n[i] > n[i + 1]
        n[i], n[i + 1] = n[i + 1], n[i]
      end
    end
  end

  n
end

OriginalL'auteur Bohr

Si vous ne souhaitez pas utiliser ce drôle de permutation de ligne (OMI):

    arr[i], arr[j] = arr[j], arr[i]

voici mon point de vue:

def bubble_sort(arr)
  temp = 0

  arr.each do |i|
    i = 0
    j = 1
    while (j < arr.length)
      if arr[i] > arr[j]
        temp = arr[i] 
        arr[i] = arr[j]
        arr[j] = temp 
        p arr
      end
    i+=1
    j+=1
    end
  end  
 arr
end

OriginalL'auteur funfuntime

De la vieille école

def bubble_sort(random_numbers)
for i in 0..random_numbers.size 
  for j in i+1..random_numbers.size-1    
    random_numbers[i], random_numbers[j] = random_numbers[j], random_numbers[i] if(random_numbers[i] > random_numbers[j])
  end
end
random_numbers
end

OriginalL'auteur Siva Kandaraj

de la classe Array 
un = [6, 5, 4, 3, 2, 1] 
n = un.longueur 

pour j de 0..n-1 
for i in 0..n - 2 - j 
si a[i]>a[i+1] 
tmp = a[i] 
a[i] = a[i+1] 
a[i+1] = tmp 
fin 
fin 
fin 

met un.inspecter 
fin

OriginalL'auteur Auwal Muhammad

Voici mon prendre l'aide de l'opérateur XOR:

def bubble(arr)
     n = arr.size - 1
     k = 1
     loop do
          swapped = false
          0.upto(n-k) do |i|
              if arr[i] > arr[i+1]
                 xor = arr[i]^arr[i+1]
                 arr[i] = xor^arr[i]
                 arr[i+1] = xor^arr[i+1]
                 swapped = true  
              end 
          end 
          break unless swapped
          k +=1 
     end
   return arr
end

OriginalL'auteur Adrian Statescu

Un autre, légèrement différente de nommage.

def bubble_sort(list)
  return list if list.size <= 1
  not_sorted = true

  while not_sorted
    not_sorted = false

    0.upto(list.size - 2) do |i|
      if list[i] > list[i + 1]
        list[i], list[i + 1] = list[i + 1], list[i]
        not_sorted = true
      end
    end
  end
  list
end

OriginalL'auteur nikkypx

 def bubbleSort(list)
  sorted = false
  until sorted
    sorted = true
    for i in 0..(list.length - 2)
      if list[i] > list[i + 1]
        sorted = false
        list[i], list[i + 1] = list[i + 1], list[i]
      end
    end
  end
  return list
end

OriginalL'auteur Anuj

Voici mon code. J'ai comme l'utilisation de la (arr.longueur-1). Pour les boucles, vous pouvez également utiliser de telles itérations exemple jusqu'à ce que, tandis que, pour d', jusqu'à boucle à faire, etc. Amusant d'essayer différentes choses pour voir comment il fonctionne.

def bubble_sort(arr)  #10/17/13 took me 8mins to write it

return arr if arr.length <= 1

sorted = true

    while sorted
     sorted = false
     (arr.length-1).times do |i|
        if arr[i] > arr[i+1]
          arr[i], arr[i+1] = arr[i+1], arr[i]
          sorted = true
        end
       end
     end
    arr
    end

OriginalL'auteur hken27

Vous devez vous connecter pour publier un commentaire.