Big O notation help

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

  1. Shibboleth

    Shibboleth teh mad Plato skillz

    Joined:
    Sep 29, 2004
    Messages:
    1,769
    Likes Received:
    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
  2. Shibboleth

    Shibboleth teh mad Plato skillz

    Joined:
    Sep 29, 2004
    Messages:
    1,769
    Likes Received:
    0
    bump, anybody?
     
  3. antiyou

    antiyou OT Supporter

    Joined:
    Jul 13, 2005
    Messages:
    25,295
    Likes Received:
    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
     
  4. Shibboleth

    Shibboleth teh mad Plato skillz

    Joined:
    Sep 29, 2004
    Messages:
    1,769
    Likes Received:
    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)}
    }
    
     

Share This Page