Сортировка в Ruby без использования метода sort

Question

Сортировка в Ruby без использования метода sort

Рейтинг: 6Ответов: 2Опубликовано: 06.10.2014

Всем доброго времени суток!

В одном из учебных материалов есть задание: напишите программу, о которой мы говорили в самом начале этой главы, которая просит нас ввести сколько угодно слов (по одному слову в строке до тех пор, пока мы не нажмём Enter на пустой строке) и которая затем повторяет нам эти слова в алфавитном порядке.

Далее есть дополнительное задание: попробуйте написать указанную программу без использования метода sort. Большая часть программирования - это преодоление сложностей, так что практикуйтесь чаще, насколько это возможно!

И здесь я застрял :( Более-менее толковое решение, подходящее на текущий этап обучения/уровень владения языком, было найдено - сортировка пузырьком:

words = ["Шарик","Бобик","Барсик","Зорька","Кеша","Арчи","Мурка"]
swap = true
size = words.length - 1
while swap
    swap = false
    for i in 0...size
        swap |= words[i] > words[i + 1] 
        words[i], words[i + 1] = words[i + 1], words[i] if words[i] > words [i + 1]
    end
    size -= 1
end
puts words.join(', ')

Данный код работает и работает правильно. Но вот проблема - не все строки мне понятны. Кто-нибудь может детально, строчку за строчкой, как для малого дитя, рассказать, что, как и почему там выполняется?

Заранее огромное спасибо!

ruby

Источник: Stack Overflow на русском

Answer 1

▲ 8Принят

Зря вы сами не писали и не разбирали алгоритм, а решили взять готовый код с недостатком знаний.

Для начала возьмем и разберемся с сортировкой и возьмем массив для примера:

words = ["Шарик","Бобик","Барсик","Зорька","Кеша","Арчи","Мурка"]

Чтобы пройтись по нему, можно использовать цикл for:

for i in 0...words.length 
  puts words[i]
end

Можно сравнивать строки с помощью обычных логических операций: words[0] > words[1]

Теперь пройдем циклом и попытаемся частично отсортировать наши данные с промежуточным выводом. Поскольку мы будем пользоваться конструкцией i+1, то чтобы не выйти за пределы массива, поменяем words.length на words.length - 1.

Для наглядности чуть изменим наш массив.

words = ["Яшка","Шарик","Бобик","Барсик","Зорька","Кеша","Арчи","Мурка"]

for i in 0...words.length - 1
   if words[i] > words[i+1] then
     temp = words[i]
     words[i] = words[i+1]
     words[i+1] = temp
   end
   puts words.join(","),"\n"
end

Вывод будет таким:

"Шарик","Яшка","Бобик","Барсик","Зорька","Кеша","Арчи","Мурка"
"Шарик","Бобик","Яшка","Барсик","Зорька","Кеша","Арчи","Мурка"
"Шарик","Бобик","Барсик","Яшка","Зорька","Кеша","Арчи","Мурка"
"Шарик","Бобик","Барсик","Зорька","Яшка","Кеша","Арчи","Мурка"
"Шарик","Бобик","Барсик","Зорька","Кеша","Яшка","Арчи","Мурка"
"Шарик","Бобик","Барсик","Зорька","Кеша","Арчи","Яшка","Мурка"
"Шарик","Бобик","Барсик","Зорька","Кеша","Арчи","Мурка","Яшка"

Как мы видим, самый маленький элемент (буква "я") пропутешествовал в конец, а другие сдвинулись к началу. Если сделать над массивом несколько таких операций, то все элементы выстроятся в отсортированный ряд.

for j in 0...words.length
  for i in 0...words.length - 1
   if words[i] > words[i+1] then
     temp = words[i]
     words[i] = words[i+1]
     words[i+1] = temp
     end
     puts words.join(","),"\n"
  end
end

В конце концов, мы получаем готовую программу сортировки пузырьком.

words = ["Яшка","Шарик","Бобик","Барсик","Зорька","Кеша","Арчи","Мурка"]

for j in 0...words.length - 1
  for i in 0...words.length - 1
   if words[i] > words[i+1] then
     temp = words[i]
     words[i] = words[i+1]
     words[i+1] = temp
    end
  end
end

puts words.join(","),"\n"

Но на самом деле этот алгоритм не идеален. Для перемены местами элементов мы используем такую конструкцию:

temp = words[i]
words[i] = words[i+1]
words[i+1] = temp

Ruby позволяет делать это проще:

words[i], words[i + 1] = words[i + 1], words[i]

К тому же у IF есть несколько вариантов синтаксиса:

if condition [then]
    code
end

и

code if condition

Во втором варианте сначала пишется один оператор и потом проверка, поэтому мы меняем наш код на аналогичный:

for j in 0...words.length - 1
  for i in 0...words.length - 1
    words[i], words[i + 1] = words[i + 1], words[i] if words[i] > words[i+1] 
  end
end

Это все один и тот же алгоритм, но записанный разными способами. Теперь разберемся с бесконечным циклом, который Вас смутил.

swap = false
while swap
   swap = true
end

Как видите, из простого примера, у нас на самом деле есть условие, это значение логической переменной swap! А теперь как оно меняется.

Есть сокращенные записи операций:

a = a + 1 аналогично a += 1
a = a * 1 аналогично  a *= 1
a |= true  аналогично a = a | true

В данном случае | является логической операцией ИЛИ которая возвращает TRUE, если хоть один из операторов содержит значение TRUE.

Данный код будет выдавать TRUE всегда, если слова не отсортированы.

for i in 0...words.length - 1
   swap |= words[i] > words[i + 1] 
end

А значит и заново запустится WHILE, если слова находятся не по порядку. А вот если они по порядку, то цикл прервется и больше не будет выполнятся. Например, для уже отсортированных слов мы пройдемся только один раз, вместо words.length раз, чем экономим себе время.

while swap
    swap = false
    for i in 0...words.length - 1
        swap |= words[i] > words[i + 1] 
        words[i], words[i + 1] = words[i + 1], words[i] if words[i] > words [i + 1]
    end
end

Во время просмотра сортировки видно, что последнее сортируемое слово уже на последнем месте, поэтому не обязательно проходится по всей длине массива. Отсюда получается size, который постоянно уменьшаем на один size -= 1. Вот так алгоритм получаем свой окончательный вид.

words = ["Шарик","Бобик","Барсик","Зорька","Кеша","Арчи","Мурка"]
swap = true
size = words.length - 1
while swap
    swap = false
    for i in 0...size
        swap |= words[i] > words[i + 1] 
        words[i], words[i + 1] = words[i + 1], words[i] if words[i] > words [i + 1]
    end
    size -= 1
end
puts words.join(', ')

Answer 2

▲ 4

Тоже долго бился над этой задачей. Суть в том, что, до этой задачи тема циклов не проходилась в этом курсе. Поэтому долго тупил... без циклов можно что-нибудь сделать? вроде бы как получилось найти "первый" элемент, и то, конечно, может неправильно в каком-нибудь случае...

name_unsort=['Pavel', 'Alla','Alena', 'Dick', 'Boris']  

length = name_unsort.length-1
max = name_unsort[length]

while (length-1) >= 0

 if max > name_unsort[length-1]
  max = name_unsort[length-1]
  length_max=length-1
  length=length-1
 else
  length=length-1
 end

end 

puts max 
#=>Alena

но потом, кажется, надо подключать рекурсию... а знаний и понимания не хватает =((

Сортировка в Ruby без использования метода sort

Ответы