Sort in Ruby without using the sort method

Question

Good day to all!

In one of the training materials there is a task: write a program about which we spoke at the very beginning of this chapter, which asks us to enter as many words as necessary (one word per line until we press Enter on an empty line) and which then repeats these words to us in alphabetical order.

Then there is an additional task: try to write the specified program without using the sort method. Most of the programming is overcoming difficulties, so practice as often as possible!

And here I was stuck: (More or less sensible solution, suitable for the current stage of learning / level of language proficiency, it was found - bubble sorting:

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(', ')

This code works and works correctly. But the problem is - not all lines are clear to me. Can anyone, in detail, line by line, as for a small child, tell what is being done, how and why?

Thank you very much in advance!

for example, in this part of swap | = words [i]> words [i + 1] it is not clear | =.
If I'm not mistaken, this is an assignment, but why is the assignment in this form?
or here: words [i], words [i + 1] = words [i + 1], words [i] if words [i] why can't you just write: words [i] = words [i + 1]?
and why, when we declare a while loop, is it not necessary to declare the condition of the loop execution?
@pirj I would like to receive a comment like this on this code: we have such an array, the default swap (?) is declared as true, the size received as the number of array elements is 1, then we have a loop while the swap ... well etc.
I am very sorry that the questions are so stupid, but I don’t just want to “swallow”, because it is necessary, and immediately, without fully understanding, to move on to another topic of study.

Vitalina eleven 1 golden mark 2 silver marks 8 bronze marks · Accepted Answer · 2014-10-07T10:39:02

In vain you yourself did not write and did not understand the algorithm, but decided to take ready-made code with a lack of knowledge.

To begin with, we will take and sort out the sorting and take an array for example:

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

To walk through it, you can use a for loop:

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

You can compare strings using common logical operations: words[0] > words[1]

Now let's go through the cycle and try to partially sort our data with intermediate output. Since we will use the i+1 construction, in order not to go beyond the array, we change words.length to words.length - 1 .

For clarity, let's slightly change our array.

 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

The output will be:

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

As we see, the smallest element (the letter "I") traveled to the end, while others moved to the beginning. If we make several such operations over an array, then all the elements will be arranged in a sorted row.

 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

In the end, we get a ready-made bubble sorting program.

 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"

But in fact, this algorithm is not perfect. To change the position of elements, we use the following structure:

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

Ruby makes it easier:

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

In addition, IF has several syntax options:

 if condition [then] code end

and

 code if condition

In the second variant, one operator is written first and then the check, so we change our code to the same one:

 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

This is all the same algorithm, but recorded in different ways. Now let's deal with the infinite loop that confused you.

 swap = false while swap swap = true end

As you can see, from a simple example, we actually have a condition, this is the value of the logical variable swap! And now how it changes.

There are abbreviated transaction records:

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

In this case | is a logical OR operation that returns TRUE if at least one of the operators contains the value TRUE.

This code will always be TRUE if the words are not sorted.

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

This means that WHILE will start again if the words are out of order. But if they are in order, the cycle will be interrupted and will no longer be executed. For example, for already sorted words we will go only once, instead of words.length times, than we save ourselves time.

 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

While viewing the sort, you can see that the last word to be sorted is already in the last place, so it does not necessarily pass through the entire length of the array. From here it turns out size , which is constantly decremented by one size -= 1 . This is how the algorithm gets its final form.

 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(', ')

Everything in my head at once on the shelves, of course, did not fit, but I am sure that after re-reading is still a couple of times, I will become as clear as possible.
And yet (honestly, I see the code in Rubi almost the first time), is it not better (in every sense, even in the number of letters) to write: ... for i in 0 ... size if words [i ]> words [i + 1] then swap = true words [i], words [i + 1] = words [i + 1], words [i] end end ... so?
@avp (0...size).each { |i| swap, words[i], words[i+1] = true, words[i+1], words[i] if words[i] > words[i+1] }
(0...size).each { |i| swap, words[i], words[i+1] = true, words[i+1], words[i] if words[i] > words[i+1] } then already.
Of course, you can always optimize, reduce, simplify, improve, but I just took an example from the textbook, from here: goo.gl/5wTya4
@pirj, frankly, it's so cool, but it’s not clear (I, for example, didn’t notice true the first time in this tuple (if such a construction is called like this in Ruby)).
It means it is possible without it (it would seem to be possible to guess, since the presence of end definitely describes everything here).
@vladchernik, oddly enough, but my main concern: swap | = words [i]> words [i + 1] lies in the plane of “micro-optimization” (the same condition is again calculated in the next line).

Pavel Zv Pavel Zv 31 1 bronze sign · Answer 2 · 2015-09-24T13:48:23

Too long struggled with this task. The bottom line is that, before this task, the topic of cycles was not covered in this course. Therefore, I was stupid for a long time ... can I do anything without cycles? it seems to be how to find the "first" element, and that, of course, may be wrong in some case ...

 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

but then, it seems, it is necessary to include recursion ... but knowledge and understanding is not enough = ((

Without cycles, you will not do anything, even your while in the code is a cycle!
But it can be done in two while loops, without any use of for ... in and recursion (this, by the way, is the topic of functions that you do not have in the program).
Simply for ... in is more convenient, but, if desired, is quietly replaced by the analogue while.

Sort in Ruby without using the sort method

2 answers 2

More articles: