Big O notation help

Discussion in 'OT Technology' started by Shibboleth, Mar 29, 2006.

Joined:
Sep 29, 2004
Messages:
1,769
0
I'm a self taught programmer, and as I result I lack any real knowledge of CS theory. I wrote a sort of reverse radix sort algorithm, and now I want to see how efficient it is. In speed tests it beats quicksort, but that doesn't mean anything unless I have it's efficiency. With my limited grasp of the theory, I've estimated it to be O(n logn).

I'll post the pith of the code below, can anyone help me out? It's in ruby btw
Also, does anyone have any resources they can point me to (not wikipedia, something geared towards teaching)? I'm also looking for good books, things to help me with theory. Thanks

Code:
```class Bsort
def initialize(container)
#below I scan for the largest number within the array
largest = 0
container.each {|x| largest = x if x > largest}

#below we find out what place the highest order bit in the largest number is
#Example: 45 is the largest number
#45 in binary = 101101
#log2 45 = 5
#the highest order bit in 45 is in the 5s place

fOrder = Math.log(largest) / Math.log(2)
order = fOrder.truncate
#here we start the sort.
#We've got to tell it where to start comparing (order)
@cont = sort(container, order)

end

def to_a
#just get the sorted array
return @cont
end

def sort(container, order)
if (container == [])
return [];
end
if (order == 0)
return []
end
gt = Array.new
lt = Array.new

container.each {|x|
#here we start the bitwise compare
#if the highest order bit is one, then add it to the greater than array
#if not, add it to the less than array
if (((x>>order) & 1) == 1)
gt<<(x)
else
lt<<(x)
end
}
#recursively sort the gt and less than arrays
#remember to decrease the bit order
return sort(lt,order-1) + sort(gt,order-1)
end
end```

Last edited: Apr 5, 2006

Joined:
Sep 29, 2004
Messages:
1,769
0
bump, anybody?

3. antiyouOT Supporter

Joined:
Jul 13, 2005
Messages:
25,295
0
Location:
in ur base
are you saying it's faster than quick sort after your initalization? since you are doing some action "for each" N times and then splitting the arrays and sorting recursively I would guess it's O of N log N which is the same as quick sort on avg, your's may perform faster in some cases and slower in others as the worst case for quick sort is N^2

Joined:
Sep 29, 2004
Messages:
1,769
0
it could just be quicksort is running into some worse case scenarios. But no, it performs better including the initialization.

here's my quicksort function for reference

Code:
```def quicksort(a)
return a if a.size <= 1
pivot = a[0]
quicksort(a.select {|value| value < pivot}) +
a.select {|value| value == pivot} +
quicksort(a.select {|value| value > pivot})
end
```
maybe if they are both O(N log N), then it's because of ruby quirks that I'm experiencing differences in bench marks

here's how I'm doing the bench mark

Code:
```1.upto(100) {container<<rand(4096)}

Benchmark.bm(100) {|r|
r.report("bSort: ") {Bsort.new(container)}
r.report("sort: ") {cont = container.sort}
r.report("qsort: ") {QuickSort.new(container)}
}
```