Class: Sorting::SmoothSort

Inherits:
Object
  • Object
show all
Extended by:
Helper
Defined in:
lib/sorting/smooth_sort.rb

Defined Under Namespace

Classes: HeapHelper

Constant Summary collapse

TEST_DATA_SIZE = 
100_000
LEONARDO_NUMBERS = 
[
  1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 
  1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735,
  150049, 242785, 392835, 635621, 1028457, 1664079, 2692537, 
  4356617, 7049155, 11405773, 18454929, 29860703, 48315633, 78176337,
  126491971, 204668309, 331160281, 535828591, 866988873, 1402817465,
  2269806339, 3672623805
]
LEONARDO_MAPPING = 

      
        
LAST_ZERO =
          
        

        
2**32 - 2


      
    

  







  
    

      Class Method Summary
      collapse
    


    
  


  
  
  
  
  
  
  
  
  
Methods included from Helper

  
sort



  

    
Class Method Details


    
      

  

  
    .sort!(data)  ⇒ Object 
  

  

  




  

    

Smooth sort Comparison sort Selection Unstable Time complexity: Ω(n), Ө(nlogn), O(nlogn) Space complexity: O(n) total, O(1) auxiliary Complicated, slow than heap sort in average and worse case



  





  



  

    
      


37
38
39
40
41
42
43
44
45

    		
    
      
# File 'lib/sorting/smooth_sort.rb', line 37

def sort!(data)
  max_i = data.size - 1
  helper = HeapHelper.new
  build_leonardo_heap data, max_i, helper
  max_i.downto(1) do |i|
    leonardo_heap_remove(data, i, helper)
  end
  nil
end