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])
