Module: Expertsort::StoogeSort

Included in:
Array
Defined in:
lib/expertsort/sorts/stoogesort.rb

Instance Method Summary collapse

Instance Method Details

#stoogesort ⇒ Object

Straight up reimplementation of the algorithm on Wikipedia.



4
5
6
 
# File 'lib/expertsort/sorts/stoogesort.rb', line 4

def stoogesort
  self.dup.stoogesort!
end

#stoogesort!(i = 0, j = self.length-1) ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/expertsort/sorts/stoogesort.rb', line 8

def stoogesort!(i = 0, j = self.length-1)
  if self[j] < self[i]
    self[i], self[j] = self[j], self[i]
  end

  if j - i + 1 >= 3
    t = (j - i + 1) / 3
    stoogesort!(i, j - t)
    stoogesort!(i + t, j)
    stoogesort!(i, j - t)
  end

  self
end