hi , some people could tell me where is the problem:
i’m a newbe of ruby , i will test some alghortim , quicksort and random
quick sort:
def quick(a,p,r)
if p<r
q=partition(a,p,r)
quick(a,p,q-1)
quick(a,q+1,r)
end
end
def partition(a,p,r)
x=a[r]
i=p-1
for j in (p…r-1)
if a[j]<=x
i=i+1
tmp=a[i]
a[i]=a[j]
a[j]=tmp
end
end
t=a[i+1]
a[i+1]=a[r]
a[r]=t
return i+1
end
def randpart(a,p,r)
i=rand(a.length)
tmp=a[r]
a[r]=a[i]
a[i]=tmp
return partition(a,p,r)
end
def randquick (a,p,r)
if p< r
q=randpart(a,p,r)
randquick(a,p,q-1)
randquick(a,q+1,r)
end
end
ranvet=[]
for i in (0…100000)
ranvet[i]=rand(10000)
end
start_time = Time.now
randquick(ranvet,0,ranvet.length-1)
total_time = Time.now - start_time
puts “tempo randomquick”
puts total_time
ranvet1=[]
for i in (0…100000)
ranvet1[i]=rand(10000)
end
start_time = Time.now
quick(ranvet1,0,ranvet.length-1)
total_time = Time.now - start_time
puts “tempo quick”
puts total_time
for a random chose of partition quicksort will be faster (look at
introduction to algorithms), why it is not?
i have make some mistake ?
or theare are some problem whit rand?
something in the interpreter?
sorry for my english!
tanks
Andrea