Всем доброго времени суток! В одном из учебных материалов есть задание: напишите программу, о которой мы говорили в самом начале этой главы, которая просит нас ввести сколько угодно слов (по одному слову в строке до тех пор, пока мы не нажмём 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(', ') Данный код работает и работает правильно. Но вот проблема - не все строки мне понятны. Кто-нибудь может детально, строчку за строчкой, как для малого дитя, рассказать, что, как и почему там выполняется? Заранее огромное спасибо!
Ответ
Зря вы сами не писали и не разбирали алгоритм, а решили взять готовый код с недостатком знаний.
Для начала возьмем и разберемся с сортировкой и возьмем массив для примера:
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(","),"
"
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(","),"
"
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(","),"
"
Но на самом деле этот алгоритм не идеален. Для перемены местами элементов мы используем такую конструкцию:
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(', ')
Комментариев нет:
Отправить комментарий