The other day I was flipping through an algorithms book and came across a section on sorting. I remembered that I had a blast writing them c++ during my undergrad and thought it would be fun to write them in a couple of different languages. I settled on writing a quicksort, and mergesort.
Interesting notes:
1) Python(2.5) returns a None type when appending a value to an empty list which forced me to use ‘+’
>>> ex= [].append()
>>> print ex
>>>None
2) Groovy gave me a java.util.ConcurrentModificationException when I transcribed my Ruby code to Groovy. Because of the fact that I was deleting items from a list that I would read in later(while loop which checks size of left and right), I got this error. Accounting for that, the groovy code is pretty nasty.(anyone that would like to provide a better example without relying on the built in Collections.sort(list) would be welcome)
Here is my code… enjoy!
# javazquez.com ==========MERGE SORT======== -------------RUBY---------------- def merge_sort(ary) return ary if (ary.length <= 1) half = ary.length/2 left = merge_sort(ary[0...half]) right = merge_sort(ary[half..ary.length-1]) result =[] #compare first left and first right while left.length > 0 and right.length > 0 result << (left[0] < right[0] ? left.shift : right.shift) end result.concat((left.length > 0 ? left : right)) return result end ary=[1,5,14,3,2,45,2,0,01,-1] p merge_sort(ary)
-----------Python Mergesort------------- def merg_sort(lst): if(len(lst) <= 1): return lst left = merg_sort(lst[:len(lst)/2]) right = merg_sort(lst[len(lst)/2:len(lst)]) result = [] while len(left) > 0 and len(right)> 0: if( left[0] > right[0]): result.append(right.pop(0)) else: result.append(left.pop(0)) if(len(left)>0): result.extend(merg_sort(left)) else: result.extend(merg_sort(right)) return result print merg_sort([8,7,43,2,5])
--------Erlang Mergesort------------- -module(mergesort). -export([ms/1,msTestSuite/1]). ms(Lst)->break(Lst). break([]) -> []; break([L]) -> [L]; break(List) -> {Left, Right} = lists:split(length(List) div 2, List), merge(break(Left),break(Right)). merge(L, []) -> L; merge([], R) -> R; merge([Lh|Ltail],[Rh|Rtail])-> if Lh < Rh -> [Lh | merge(Ltail,[Rh|Rtail])]; Lh >= Rh -> [Rh | merge(Rtail,[Lh|Ltail])] end. %to test, run mergesort:msTestSuite(run). msTestSuite(run)-> [mstest1(run),mstest2(run), mstest3(run),mstest4(run), mstest5(run)]. mstest1(run)-> ms([3,2,1]). mstest2(run)-> ms([3,3,3,1]). mstest3(run)-> ms([]). mstest4(run)-> ms([1]). mstest5(run)-> ms([123,0,-1,23,2,34,5,678,7,5,8]).
-------------GROOVY MERGESORT-------- def ms(lst){ if(lst.size() <= 1){return lst} def sz=lst.size() int half = (int)(sz/2) def l = lst [ 0 .. < half] def r = lst [ half.. < sz] def lft = ms(l) def rht = ms(r) def result = [] def rcnt = 0 def lcnt = 0 while( lcnt < lft.size() && rcnt < rht.size()){ if(lft[lcnt] < rht[rcnt]){ result += lft[lcnt++] } else{ result += rht[rcnt++] } } if(lcnt < lft.size()){ result += ms(lft[lcnt..< lft.size()]) } else{ result += ms(rht[rcnt..< rht.size()]) } return result } sl=[3,88,5,3,2,1,-2,2] println ms(sl)
# javazquez.com ========QUICKSORT======== -----RUBY---------------- def quick_sort(ary) return ary if(ary.length <= 1) greater,less = [],[] pos = rand(ary.length) pivot = ary[pos] ary.delete_at(pos) ary.each{|item| (item < pivot) ? less << item :greater << item} return (quick_sort(less) << pivot).concat(quick_sort(greater)) end ary=[1,5,14,3,2,45,2,0,01,-1] p quick_sort(ary)
----------Python Quicksort-------------- import random def quickSort(lst): if(len(lst) <= 1):return lst greater = [] less = [] pivot = lst.pop(random.randint(0,len(lst)-1)) for item in lst: if(item < pivot): less.append(item) else: greater.append(item) return quickSort(less)+[pivot]+quickSort(greater) ary=[1,5,14,3,2,45,2,0,01,-1]
----------Erlang Quicksort-------------- -module(quicksort). -export([qsort/1]). qsort([]) ->[]; qsort([Pivot|T]) -> lists:append( [qsort([X || X <- T, X < Pivot]), [Pivot], qsort([X || X <- T, X >= Pivot]) ). -------GROOVY QUICKSORT-------------- def quickSort(lst){ if(lst.size() <= 1){return lst} def greater = [] def less = [] def pivot = lst.remove(new Random().nextInt(lst.size())) lst.each{item-> if(item < pivot){ less.add(item)} else{greater.add(item)} } return quickSort(less)+[pivot]+quickSort(greater) } print quickSort([1,5,14,3,2,45,2,0,01,-1])
This is a working and clear groovy mergsort
def ms(lst){
def sz=lst.size()
if(sz <= 1)
return lst
def half = (int)(sz/2)
def lft = ms(lst[0..<half])
def rht = ms(lst[half..sz-1])
def rcnt = 0
def rlen = sz -half
def result =[]
lft.each {lf->
while (rcnt < rlen && rht[rcnt] <= lf)
result += rht[rcnt++]
result += lf
}
while (rcnt < rlen)
result += rht[rcnt++]
return result
}
sl=[3,88,5,3,2,1,-2,2]
println ms(sl)
Thanks for the submission George 😀
Hey, cool tips. Perhaps I’ll buy a bottle of beer to that person from that forum who told me to visit your blog 🙂
——-GROOVY QUICKSORT————–
def quickSort(List lst) {
if (lst.size() <= 1) return lst
def (less, greater) = [[], []]
def pivot = lst.remove(new Random().nextInt(lst.size()))
lst.each {
if (it < pivot) less << it
else greater << it
}
quickSort(less) + pivot + quickSort(greater)
}
Instead of random parameter you can use (list.size() / 2)