TAG | python
3
Mergesort and Quicksort with Dynamic Languages
4 Comments · Posted by admin in Erlang, Groovy, Ruby, code, python
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..# 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])
algorithm · algorithms · code · Erlang · Groovy · mergesort · Programming · python · quicksort · Ruby · sort · sorting
Yesterday I decided to play with Gmail’s API in order to grab my contacts. To my surprise, it was a snap. Google has instructions for python Here, I wrote my example using Python 2.5 on OS X. Once I had unzipped the GData contents, I just changed to the GData directory and ran
“sudo python setup.py install”
and I was ready to go.
Python Documentation for GDATA
#################################
# javazquez.com
# Google GMAIL API example
##################################
import gdata.contacts.service
user = 'user@gmail.com'
pwd = 'password'
client2 = gdata.contacts.service.ContactsService()
# Authenticate using your Google Docs email address
# and password.
client2.ClientLogin(user, pwd)
contacts_feed = client2.GetContactsFeed()
################################################
# NOTE: The GetContactsFeed does not give back
# all contacts.
# This 'problem' can be solved by looping
# until the contacts_feed.GetNextLink
# returns None.
################################################
l=[]
while(contacts_feed) :
for x in contacts_feed.entry:
l.append([x.title.text, x.email[0].address])
ret = contacts_feed.GetNextLink()
contacts_feed = client2.GetContactsFeed(ret.href) if(ret) else ret
print "here are your %d contacts" % len(l)
for contact in l:
print "%s -> %s" % (contact[0],contact[1])
pre>
Output
here are your xxxx contacts
ANDREW -> adrew@somewhere.com
...
code · google api · python
If your like me, you bounce around between languages a lot. Lately, I have been writing python code. It’s not Ruby
, but it can get the job done. Here is a quick list of similarities between the two languages. I hope it helps… don’t forget to this list in the comments section ![]()
#-----find object methods-----
s="hello, I am a string"
#ruby
puts s.methods
#python
print dir(s)
#find out more about a method using python
help(s.split)
#-----view object's class-----
#ruby
s.class
#python
s.__class__
#------Iterate hashes-------
#ruby
h.each{|key,value| puts "#{key}, #{value}"}
#python
for key,value in h.iteritems():
print key, value
#---ternary operators
#ruby
condition ? var = x : var = y
#python.. not exactly an operator, but you get the meaning
#---- var = y if condition is false
var = x if condition else y
#----lengths------
#ruby
s="hello, I am a string"
puts "Length of string is #{s.length} or #{s.size}"
h={:one=>2,:three=>4}
puts "Length of hash is same as string, #{h.length} or #{h.size} "
#python
print("This is the length of a string %s" % len("string"))
print("number of key/value pair= %d" % len({'one':1,'two':2}))
#---slicing lists/arrays
l=[1,2,3,4,5]
#ruby
l[1..3] #=>[2,3]
#python
l[1:3] #=>[2,3]
#--print string multiple times-----
#ruby
4.times{print "hello"} #=> hellohellohellohello
#python
print("hello" * 4) #=> hellohellohellohello
code · fun · Programming · python · Ruby · Ruby Questions
I love to learn and try new languages. Not only is learning a new language fun, many times it teaches me something new about a language that I am already familiar with. The only problem that I have with learning so many languages, is keeping them straight. I decided that I would take a few of the dynamic languages I use most often and compile a list of how to handle File I/O with each of them. If you have a Dynamic language(part 2 of this post will be on static languages) not represented below or have another method of File I/O with the represented languages, please add to the list with its respective File I/O code:D
Without further ado…
//Groovy open file for writing
def target ="filename"
File wf= new File(target)
wf.write( "I am in your file eating your space" )
//Groovy open file for appending
def target ="filename"
File af= new File(target)
af.append("I have all of your base")
//Groovy read each line in file
new File("filename").eachLine{line-> println line}
//Groovy read whole document and put into List
List lines = new File("filename").readLines()
//lines contains two lines that we need
println "first line $lines[0]"
println "second line $lines[1]"
//Groovy reading one line
File rf= new File("filename") //open for reading
//read first line, trim, assign to tmp
rf.withReader { line ->tmp = line.readLine().trim()}
//Groovy test if file exists
File src = new File(srcFile)
if (src.exists() ){ println "I exist"}
else{println "I don't exist"}
#Ruby openfile for reading
fh = File.new(path, "r") # open file "path" for reading only
fh.close
#Ruby open file for writing
fout = File.new(path, "w") # open file "path" for writing only
fout.puts "Up, Up, Down, Down, Left, Right, Left, Right, B, A, Select, Start"
fout.close
#Ruby open file for apending
fa= File.new("DeleteMe.txt","a")
fa.puts "I am at the end of file"
fa.close
#Ruby read eachline in a file
File.open("file").each { |line| p line}
#Ruby read entire file to string
fh = File.new(filename)
str = fh.read
#Ruby read entire file into array(each line is an element in the array)
fh = File.new(filename)
str = fh.readlines
#Python Write a file
fout = open("DeletMe.txt", "w")
fout.write("Writing to fout\nCheck it out!")
fout.close()
#Python Read an entire file
fin = open("ReadingTest.txt", "r")
fin_text = fin.read()
fin.close()
print fin_text
#Python read entire file into list
fin = open("ReadingTest.txt", "r")
txt= fin.readlines()
fin.close()
print txt[0]
#Python append to a file
fh= open ( 'DeleteMe.txt', 'a' )
fh.write ( '\n\n\nBottom line.' )
fh.close()
#Perl reading a file
open(FILE, '<', $file) or die "Can't read $file: $!\n";
while(<FILE>)
{
print ;
}
#Perl append to a file
open(FILE, '>>', $file) or die "Can't append to $file: $!\n";
print FILE "text";
close(FILE);
#Perl read and write to a file
#+< allows reading and writing, and keeps the data that was
#already in the file. open() will fail if file doesn't exist.
open(FILE, "+<$file" ) or die ("Can't read|write: $file\n");
close(FILE);
#Perl read and write to a file
#+>allows writing and reading, but replaces/overwrites the
#data in the file if the file exists. Creates it if it doesn't exist.
open(FILE, "+>$file" ) or die ("Can't write or read:$file \n");
close(FILE);
PHP code doesn’t display properly within WordPress, so here is an image of the code

