Alphabetical sorting of an array without using the sort method

Question

I have been working through Chris Pine's tutorial for Ruby and am currently working on a way to sort an array of names without using sort.

My code is below. It works perfectly but is a step further than I thought I had got!

puts "Please enter some names:"

name = gets.chomp

names = []

while name != ''

    names.push name

    name = gets.chomp

end

names.each_index do |first|
  names.each_index do |second|
        if names[first] < names[second]
            names[first], names[second] = names[second], names[first]
        end

  end
end

puts "The names you have entered in alphabetical order are: " + names.join(', ') 

It is the sorting that I am having trouble getting my head around.

My understanding of it is that each_index would look at the position of each item in the array. Then the if statement takes each item and if the number is larger than the next it swaps it in the array, continuing to do this until the biggest number is at the start. I would have thought that this would just have reversed my array, however it does sort it alphabetically.

Would someone be able to talk me through how this algorithm is working alphabetically and at what point it is looking at what the starting letters are?

Thanks in advance for your help. I'm sure it is something very straightforward but after much searching I can't quite figure it out!

Answer 1

I think the quick sort algorithm is one of the easier ones to understand:

def qsort arr
  return [] if arr.length == 0
  pivot = arr.shift
  less, more = arr.partition {|e| e < pivot }
  qsort(less) + [pivot] + qsort(more)
end

puts qsort(["George","Adam","Michael","Susan","Abigail"])

The idea is that you pick an element (often called the pivot), and then partition the array into elements less than the pivot and those that are greater or equal to the pivot. Then recursively sort each group and combine with the pivot.

Answer 2

Your understanding is just a bit off.

You said:

Then the if statement takes each item and if the number is larger than the next it swaps it in the array

But this is not what the if statement is doing.

First, the two blocks enclosing it are simply setting up iterators first and second, which each count from the first to the last element of the array each time through the block. (This is inefficient but we'll leave discussion of efficient sorting for later. Or just see Brian Adkins' answer.)

When you reach the if statement, it is not comparing the indices themselves, but the names which are at those indices.

You can see what's going on by inserting this line just before the if. Though this will make your program quite verbose:

puts "Comparing names[#{first}] which is #{names[first]} to names[#{second}] which is #{names[second]}..."

Answer 3

I can see why you're puzzled -- I was too. Look at what the algorithm does at each swap. I'm using numbers instead of names to make the order clearer, but it works the same way for strings:

names = [1, 2, 3, 4]

names.each_index do |first|
  names.each_index do |second|
    if names[first] < names[second]
      names[first], names[second] = names[second], names[first]
      puts "[#{names.join(', ')}]"
    end
  end
end

=>

[2, 1, 3, 4]
[3, 1, 2, 4]
[4, 1, 2, 3]
[1, 4, 2, 3]
[1, 2, 4, 3]
[1, 2, 3, 4]

In this case, it started with a sorted list, then made a bunch of swaps, then put things back in order. If you only look at the first couple of swaps, you might be fooled into thinking that it was going to do a descending sort. And the comparison (swap if names[first] < names[second]) certainly seems to imply a descending sort.

The trick is that the relationship between first and second is not ordered; sometimes first is to the left, sometimes it's to the right. Which makes the whole algorithm hard to reason about.

This algorithm is, I guess, a strange implementation of a Bubble Sort, which I normally see implemented like this:

names.each_index do |first|
  (first + 1...names.length).each do |second|
    if names[first] > names[second]
      names[first], names[second] = names[second], names[first]
      puts "[#{names.join(', ')}]"
    end
  end
end

If you run this code on the same array of sorted numbers, it does nothing: the array is already sorted so it swaps nothing. In this version, it takes care to keep second always to the right of first and does a swap only if the value at first is greater than the value at second. So in the first pass (where first is 0), the smallest number winds up in position 0, in the next pass the next smallest number winds up in the next position, etc.

And if you run it on array that reverse sorted, you can see what it's doing:

[3, 4, 2, 1]
[2, 4, 3, 1]
[1, 4, 3, 2]
[1, 3, 4, 2]
[1, 2, 4, 3]
[1, 2, 3, 4]

Finally, here's a way to visualize what's happening in the two algorithms. First the modified version:

  0  1  2  3
0    X  X  X
1       X  X
2          X
3

The numbers along the vertical axis represent values for first. The numbers along the horizontal represent values for second. The X indicates a spot at which the algorithm compares and potentially swaps. Note that it's just the portion above the diagonal.

Here's the same visualization for the algorithm that you provided in your question:

  0  1  2  3
0 X  X  X  X
1 X  X  X  X
2 X  X  X  X
3 X  X  X  X

This algorithm compares all the possible positions (pointlessly including the values along the diagonal, where first and second are equal). The important bit to notice, though, is that the swaps that happen below and to the left of the diagonal represent cases where second is to the left of first -- the backwards case. And also note that these cases happen after the forward cases.

So essentially, what this algorithm does is reverse sort the array (as you had suspected) and then afterwards forward sort it. Probably not really what was intended, but the code sure is simple.

Answer 4

Alternatively, you can create a new array and use a while loop to append the names in alphabetical order. Delete the elements that have been appended in the loop until there are no elements left in the old array.

sorted_names = []

while names.length!=0
    sorted_names << names.min
    names.delete(names.min)
end

puts sorted_names

Answer 5

This is the recursive solution for this case

def my_sort(list, new_array = nil)

  return new_array if list.size <= 0
  if new_array == nil
    new_array = []
  end
  min = list.min
  new_array << min
  list.delete(min)

  my_sort(list, new_array)

end

puts my_sort(["George","Adam","Michael","Susan","Abigail"])

Answer 6

Here is my code to sort items in an array without using the sort or min method, taking into account various forms of each item (e.g. strings, integers, nil):

def sort(objects)
    index = 0
    sorted_objects = []
  while index < objects.length
      sorted_item = objects.reduce do |min, item|
        min.to_s > item.to_s ? item : min
      end
      sorted_objects << sorted_item
      objects.delete_at(objects.find_index(sorted_item))
  end
  index += 1
  sorted_objects
end



words_2 = %w{all i can say is that my life is pretty plain}
p sort(words_2)
=> ["all", "can", "i", "is", "is", "life", "my", "plain", "pretty", "say", "that"]

mixed_array_1 = ["2", 1, "5", 4, "3"]
p sort(mixed_array_1)
=> [1, "2", "3", 4, "5"]

mixed_array_2 = ["George","Adam","Michael","Susan","Abigail", "", nil, 4, "5", 100]
p sort(mixed_array_2)
=> ["", nil, 100, 4, "5", "Abigail", "Adam", "George", "Michael", "Susan"]