Life as Clay

Learn to Program: Sorting Algorithm code

with 3 comments


I’ve been working through the 1st edition of Chris Pine’s book “Learn to Program,” based on Ruby. The first substantial challenge in the book is designing an algorithm to sort a list of words entered. I thought I had it complete when I realized that if I entered multiples of the same word, some uppercase and some lowercase, that it would not sort the variations of that word properly. So, I started to put debug comments in the code so that I could follow along. The debug code is marked – you can comment it out to see the results returned immediately.

What happens: I start with an unsorted list. I take the last entry in the list and compare it to the next-to-last entry. If the last entry should come before the next-to-last entry, I pop the last entry to a temp variable and pop/push the next-to-last entry to an array called ‘holder,’ then push the entry that we’re holding in the temp variable back onto the end of the original unsorted array because I now know that it deserves to be closer to the front of the list than it was.

If the last entry deserves, in fact, to be lower down the list than the next to last entry, I pop/push it to the holder array.

If the last entry.downcase is the same as the next to last entry.downcase, then I compare them in their original form to determine which should come first (capital letters should come first), and use the same process as above to move the appropriate one to the holder array. If they truly are equal, then I just move the last entry to the holder array.

I loop through this x times, where x = the number of items in the unsorted list minus 1 (or the number of comparisons that we have to do to leave the original list with only one entry – the alphabetical first from the original unsorted list). The sorted list becomes the previous sorted list + the list that we just sorted through (now with one entry). In other words, I append the next alphabetical list item to the end of the sorted list. I then call recursion where I pass in the holder array as the unsorted list and the previously sorted list + the appended next-alphabetical-item as the sorted list. Hence, each recursion finds the item with alphabetical precedence and appends it to the end of the sorted list.

When recursion is called and the unsorted list is empty, I exit the method by returning the sorted list and then display it on the screen.

Thoughts and comments are welcome, though I’m somewhat of a programming newbie, so I probably won’t be able to answer any difficult questions.

def sort some_array
  recursive_sort some_array, []
end

def recursive_sort unsorted_array, sorted_array

  # We're done, return the result.
  if unsorted_array.length == 0
    puts 'Here is the final list, sorted.'
    return sorted_array.join(', ')

  else
    holder = []
    x = unsorted_array.length - 1 # number of comparisons down the list we have to do

    x.times do
      if unsorted_array[x].downcase < unsorted_array[x-1].downcase
        puts 'Case 1: Last item deserved to be before the next-to-last item.' # debug code
        temp = unsorted_array.pop
        holder.push unsorted_array.pop
        unsorted_array.push temp

      elsif unsorted_array[x].downcase > unsorted_array[x-1].downcase
        puts 'Case 2: Next-to-last item deserved to be where it is...' # debug code
        holder.push unsorted_array.pop

      elsif unsorted_array[x].downcase == unsorted_array[x-1].downcase
        puts 'Case 3: Downcase of the last and next-to-last are equal, testing their regular forms...' # debug code

        if unsorted_array[x] < unsorted_array[x-1]
          puts 'Case 3a: In original form, the last item deserves to come before the next to last item.' # debug code
          temp = unsorted_array.pop
          holder.push unsorted_array.pop
          unsorted_array.push temp

        elsif unsorted_array[x] >= unsorted_array[x-1]
          puts 'Case 3b: In original form, the next-to-last item either is equal to the last item or deserves to be where it is...' # debug code
          holder.push unsorted_array.pop
        end
      end

      x = unsorted_array.length - 1 # Updating the number of comparisons we have to do.

      puts 'Working list (unsorted_array): ' + unsorted_array.join(', ') # debug code
      puts 'Unsorted (holder): ' + holder.join(', ') # debug code
      puts # debug code
      puts 'Master sorted list: ' + sorted_array.join(', ') # debug code
      puts # debug code
      puts 'Press return to continue.' # debug code
      gets # This causes code execution to halt until you press return so that you can read the output.

    end

  end

  sorted_array = sorted_array + unsorted_array # Appending the next item to the sorted list.

  puts # debug code
  puts 'Recursing...' # debug code
  puts # debug code

  recursive_sort(holder,sorted_array) # Recursion Line

end

puts 'Enter words, and a blank return when finished:'
entry = gets.chomp
list = []

while entry != ""
  list.push entry
  entry = gets.chomp
end

puts sort(list)

And in its uncommented form:

def sort some_array
  recursive_sort some_array, []
end

def recursive_sort unsorted_array, sorted_array
  if unsorted_array.length == 0
    puts 'Here is the final list, sorted.'
    return sorted_array.join(', ')
  else
    holder = []
    x = unsorted_array.length - 1
    
    x.times do
      
      if unsorted_array[x].downcase < unsorted_array[x-1].downcase
        temp = unsorted_array.pop
        holder.push unsorted_array.pop
        unsorted_array.push temp
      elsif unsorted_array[x].downcase > unsorted_array[x-1].downcase
        holder.push unsorted_array.pop
      elsif unsorted_array[x].downcase == unsorted_array[x-1].downcase
              
        if unsorted_array[x] < unsorted_array[x-1]
          temp = unsorted_array.pop
          holder.push unsorted_array.pop
          unsorted_array.push temp          
        elsif unsorted_array[x] >= unsorted_array[x-1]
          holder.push unsorted_array.pop
        end
        
      end
      
      x = unsorted_array.length - 1
    end
    
  end
  
  sorted_array = sorted_array + unsorted_array
  recursive_sort(holder,sorted_array)
end

puts 'Enter words, and a blank return when finished:'
entry = gets.chomp
list = []

while entry != ""
  list.push entry
  entry = gets.chomp
end

puts sort(list)
Advertisements

Written by Clay

October 3, 2009 at 13:44

Posted in Code, Ruby

Tagged with , , ,

3 Responses

Subscribe to comments with RSS.

  1. With regards to optimization, I realize that Case 3a and Case 3b could be made part of OR statements for Case 1 and Case 2, but I don’t know whether it’s better to evaluate an OR statement in an IF statement or to just evaluate IF statements…

    Clay

    October 3, 2009 at 16:20

  2. I take that back… I tried and it didn’t work. Maybe it needs an AND statement instead – or just the nested IF statements, which is what I already have.

    Clay

    October 3, 2009 at 16:51

  3. […] it, but he chose not to in the text. Faced with a similar challenge in a Ruby programming book, I wrote a method that would properly handle such […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: