Understanding sorting algorithm by just reading text or still illustration takes a lot of mind gymnastic. Apparently, there are lot of videos online, trying to explain the concept. But not all explain it as good though, some with really boring animation, some with crappy background music, and some even both, 
. Here are two that I find did a great job in explaining bubble sort,
This one from codegearguru. Instead of creating graphic, or cutting out paper to represent data in the sorting process, just use the poker cards! That seems obvious now, but I didn’t think about it when I try to illustrate sorting to myself initially. Ha. Think there is a series of video created for different type of sorting algorithm as well, so definitely a great tool to understand sorting algorithm. Bonus near the end of the video, another technique called shaker sort or cocktail sort is also explained, which is basically a bidirectional bubble sort which should speed up the sorting speed.
Another one from Miles Hauskaz, just plain simple and succinct explanation and a video nicely done as well.
Sorting Algorithms – Bubble Sort from Miles Hauskaz on Vimeo.
So, this is my implementation of bubble sort, admittedly not the best that you can find, but that will do for me now, until I have time to come back and do some refactoring.
arr = %w{g a c b j e e} i = arr.length - 1 count = 0 n = arr.length - 1 def swap(m,n) arr = [] if m > n arr << n arr << m else arr << m arr << n end end while n > 0 while count < i puts "comparing #{arr[count]} to #{arr[count+1]}" a = swap(arr[count],arr[count+1]) arr[count..count+1] = a count += 1 end n -= 1 i -= 1 count = 0 end p arr
It is a bit difficult for me to understand the difference between map and each, until I found out this in irb accidentally,
irb(main):001:0> name = %w{guido knuth adrian dhh pg} => ["guido", "knuth", "adrian", "dhh", "pg"] irb(main):002:0> name.each {|n| n.upcase} => ["guido", "knuth", "adrian", "dhh", "pg"] irb(main):003:0> name.map {|n| n.upcase} => ["GUIDO", "KNUTH", "ADRIAN", "DHH", "PG"]
map and each are suppose to do almost the same thing, but why each didn’t return the correct result in uppercase like what map did?
The different is each yield each element in the collection to the code block, in this case perform the upcase method, but return the receiver, which is the original array, hence an array of lower case names.
Whereas, map return a new array, consists of elements already went through the code block, hence an array of upper case names.
irb(main):007:0> name.each {|n| p n.upcase} "GUIDO" "KNUTH" "ADRIAN" "DHH" "PG" => ["guido", "knuth", "adrian", "dhh", "pg"] irb(main):006:0> name.map {|n| p n.upcase} "GUIDO" "KNUTH" "ADRIAN" "DHH" "PG" => [nil, nil, nil, nil, nil]
So here you can see with p, both map and each output the uppercase names, but look more carefully, the return value of each, as expected, is the original array. map however, return an array of nils!
Why is that?
Okay, much better only in a relative term, comparing to my earlier sorting which didn’t take care of duplicate elements.
Two major changes here.
- I do away with the temporary variable for holding on the smallest number result from each round of the comparison, instead elements are now passed over directly to the sorted array.
- Those elements that get passed to the sorted array, will be deleted from the original array, but one items at one round of comparison, which mean if there are duplicated elements, only one of the instance will be removed.
hackers.delete_at(hackers.index(sorted[count]))
It look a lot more wordy than a shorter
hackers.delete(sorted[count])
but this is deleting ONLY the first element that match the value, compare to the shorter version where it will remove all elements. So it preserve the other element for next round of comparison, and eventually make it to the sorted array.
Complete code as below,
hackers = %w{ gosling matz dhh adrian guido matz knuth dhh adrian guido } i = hackers.length count = 0 sorted = [] while count < i sorted[count] = hackers.inject{ |a,b| a < b ? a : b } p sorted[count] hackers.delete_at(hackers.index(sorted[count])) count += 1 end p sorted
And the result….
["adrian", "adrian", "dhh", "dhh", "gosling", "guido", "guido", "knuth", "matz", "matz"]
Finally have the time to come back to the sorting exercise, here is a slightly better version of sort.
It still doesn’t take care of duplicate elements, but compare to the first sorting version, this one is shorter, as the whole finding smallest element left in the array is now done by inject and a ternary operator, a whole 7 lines of code cut to just 1. And now it no longer sort animals, it sort a list of hackers 
hackers = %w{matz ddh adrian guido gosling knuth linus} i = hackers.length sorted = [] while i > 0 small = hackers.inject{ |a,b| a < b ? a : b} sorted.push small hackers.delete small i -= 1 end p sorted
And the result of the sort is
["adrian", "ddh", "gosling", "guido", "knuth", "linus", "matz"]
So the next iteration will be to take care of duplicated elements…stay tuned.
Apparently you can have optional parameter listed in the middle for your method in Ruby version 1.9
C:\>pik switch 191 C:\>irb irb(main):001:0> def talk(a,*b,c) irb(main):002:1> p a,b,c irb(main):003:1> end => nil irb(main):004:0> talk 'a','b','c' "a" ["b"] "c" => ["a", ["b"], "c"]
but not Ruby version 1.8.7
C:\>pik switch 187 C:\>irb irb(main):001:0> def talk(a,*b,c) irb(main):002:1> p a,b,c irb(main):003:1> end SyntaxError: compile error (irb):1: syntax error, unexpected tIDENTIFIER, expecting tAMPER or '&' def talk(a,*b,c) ^ from (irb):1 irb(main):004:0> quit
A beautiful visualization of sorting algorithm…
via Hacker News
Another way for factorial, extending the integer class, so the function will feel more natural, instead of fact 6 for example, you just call it by 6.fact.
Also, added a function to sum up the factorial value, counting down. Example, for 6!, it will be 6! + 5! + 4! + 3! + 2! + 1!
Here go,
class Integer def fact if self == 0 return 1 else n = self * (self - 1).fact end end def sum_fact (1..self).inject{|a,b| a + self.fact} end end puts 4.fact puts 4.sum_fact
Hours ago I got a programming test question about factorial, which I didn’t do really well, only completed with the help of the interviewer. Damn.
The worst thing is that I have done this question before, and I know in the head I can use recursion for it, but I totally go blank on how to do it with recursion. Here go my chance…sigh…
Now, here is how factorial can be done.
With Recursion.
def fact n if n == 0 1 else n = n * fact(n-1) end end
That simple.
Factorial without recursion, using inject instead
def fact n if n == 0 1 else (1..n).inject { |a,b| a*b } end end
Isn’t that difficult, huh? What was I thinking?!
Am running through “Learn to Program” from Chris Pine, again.
I have been cracking my head on the exercise to write a sort method instead of just using the array#sort come with ruby.
As the exercise actually came at the stage of the tutorial that more advanced techniques like ternary operator is yet to be introduced, so I figure I might want to limit myself to use only the basic while and if.There are some blog posts, discussion in forums on the solution to this question.
Someone suggest to read about sorting algorithm before attempting to solve the question, a brief search yields all sorts of sort (ha!), insertion, selection, bubble, shell, merge, heap, quick, just for sorting. As sorting always require brain gymnastic trying to imagine the on going process (at least for me), there are animations available for all these different type of sort. Although, frankly I still couldn’t really get a grasp after watching those animations.
As I read from Renae’s blog that they are using paper cutouts, while I have been sketching and sketching and sketching trying to illustrate the flow.
And so, here is my attempt to the problem, it is rather coarse, it didn’t use method, it can’t deal with duplicate elements in the array, so, there are still a lot of be improve on, when I have time on it. Nevertheless, here it is
animals = ['cat','bird','a','mouse','bull','elephant','dog'] unsorted = animals.dup sorted= [] i = animals.length - 1 smaller = animals[i] while unsorted.length != 0 while i >= 0 if smaller < animals[i] smaller else smaller = animals[i] end i = i - 1 end sorted.push smaller unsorted.delete smaller animals.delete smaller smaller = unsorted[i] i = unsorted.length - 1 end puts sorted.inspect
a = [9,5,6,3,7] a.sort { |x,y| x==5? 1:x<=>y } [3, 6, 7, 9, 5]
So, I sort the array consisting 9,5,6,3,7, run it through a block, put the elements to x and y then sort it in ascending order, except for the number “5″, which will be stuck at the end of the order.
But why in the case below then the number “2″ which should be at the end of the order is instead at the second last place?
c = [22,77,88,55,44,11,2,8] c.sort { |x,y| x==2? 1:x<=>y } [8, 11, 22, 44, 55, 77, 2, 88]
I tried to sort a few different arrays, and sometimes the second case just pop up, which still puzzling me. Why the different?