Module Algorithms::Sort

  1. lib/algorithms/sort.rb

This module implements sorting algorithms. Documentation is provided for each algorithm.

Public class methods

bubble_sort (container)

Bubble sort: A very naive sort that keeps swapping elements until the container is sorted. Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should be implemented for the container. Time Complexity: О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes

Algorithms::Sort.bubble_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
[show source]
    # File lib/algorithms/sort.rb, line 16
16:   def self.bubble_sort(container)
17:     loop do
18:       swapped = false
19:       (container.size-1).times do |i|
20:         if (container[i] <=> container[i+1]) == 1
21:           container[i], container[i+1] = container[i+1], container[i] # Swap
22:           swapped = true
23:         end
24:       end
25:       break unless swapped
26:     end
27:     container
28:   end
comb_sort (container)

Comb sort: A variation on bubble sort that dramatically improves performance. Source: yagni.com/combsort/ Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should be implemented for the container. Time Complexity: О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes

Algorithms::Sort.comb_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
[show source]
    # File lib/algorithms/sort.rb, line 39
39:   def self.comb_sort(container)
40:     container
41:     gap = container.size
42:     loop do
43:       gap = gap * 10/13
44:       gap = 11 if gap == 9 || gap == 10
45:       gap = 1 if gap < 1
46:       swapped = false
47:       (container.size - gap).times do |i|
48:         if (container[i] <=> container[i + gap]) == 1
49:           container[i], container[i+gap] = container[i+gap], container[i] # Swap
50:           swapped = true
51:         end
52:       end
53:       break if !swapped && gap == 1
54:     end
55:     container
56:   end
heapsort (container)

Heap sort: Uses a heap (implemented by the Containers module) to sort the collection. Requirements: Needs to be able to compare elements with <=> Time Complexity: О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes

Algorithms::Sort.heapsort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
[show source]
    # File lib/algorithms/sort.rb, line 85
85:   def self.heapsort(container)
86:     heap = Containers::Heap.new(container)
87:     ary = []
88:     ary << heap.pop until heap.empty?
89:     ary
90:   end
insertion_sort (container)

Insertion sort: Elements are inserted sequentially into the right position. Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should be implemented for the container. Time Complexity: О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes

Algorithms::Sort.insertion_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
[show source]
     # File lib/algorithms/sort.rb, line 100
100:   def self.insertion_sort(container)
101:     return container if container.size < 2
102:     (1..container.size-1).each do |i|
103:       value = container[i]
104:       j = i-1
105:       while j >= 0 and container[j] > value do
106:         container[j+1] = container[j]
107:         j = j-1
108:       end
109:       container[j+1] = value
110:     end
111:     container
112:   end
merge (left, right)
[show source]
     # File lib/algorithms/sort.rb, line 230
230:   def self.merge(left, right)
231:     sorted = []
232:     until left.empty? or right.empty?
233:       left.first <= right.first ? sorted << left.shift : sorted << right.shift
234:     end
235:     sorted + left + right
236:   end
mergesort (container)

Mergesort: A stable divide-and-conquer sort that sorts small chunks of the container and then merges them together. Returns an array of the sorted elements. Requirements: Container should implement [] Time Complexity: О(n log n) average and worst-case Space Complexity: О(n) auxiliary Stable: Yes

Algorithms::Sort.mergesort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
[show source]
     # File lib/algorithms/sort.rb, line 222
222:   def self.mergesort(container)
223:     return container if container.size <= 1
224:     mid   = container.size / 2
225:     left  = container[0...mid]
226:     right = container[mid...container.size]
227:     merge(mergesort(left), mergesort(right))
228:   end
partition (data, left, right)

Quicksort: A divide-and-conquer sort that recursively partitions a container until it is sorted. Requirements: Container should implement pop and include the Enumerable module. Time Complexity: О(n log n) average, O(n^2) worst-case Space Complexity: О(n) auxiliary Stable: No

Algorithms::Sort.quicksort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]

def self.quicksort(container)

return [] if container.empty?

x, *xs = container

quicksort(xs.select { |i| i <  x }) + [x] + quicksort(xs.select { |i| i >= x })

end

[show source]
     # File lib/algorithms/sort.rb, line 154
154:   def self.partition(data, left, right)
155:     pivot = data[front]
156:     left += 1
157: 
158:     while left <= right do
159:       if data[frontUnknown] < pivot
160:         back += 1
161:         data[frontUnknown], data[back] = data[back], data[frontUnknown] # Swap
162:       end
163: 
164:       frontUnknown += 1
165:     end
166: 
167:     data[front], data[back] = data[back], data[front] # Swap
168:     back
169:   end
quicksort (container)

def self.quicksort(container, left = 0, right = container.size - 1)

if left < right
  middle = partition(container, left, right)
  quicksort(container, left, middle - 1)
  quicksort(container, middle + 1, right)
end

end

[show source]
     # File lib/algorithms/sort.rb, line 180
180:   def self.quicksort(container)
181:     bottom, top = [], []
182:     top[0] = 0
183:     bottom[0] = container.size
184:     i = 0
185:     while i >= 0 do
186:       l = top[i]
187:       r = bottom[i] - 1;
188:       if l < r
189:         pivot = container[l]
190:         while l < r do
191:           r -= 1 while (container[r] >= pivot  && l < r)
192:           if (l < r)
193:             container[l] = container[r]
194:             l += 1
195:           end
196:           l += 1 while (container[l] <= pivot  && l < r)
197:           if (l < r)
198:             container[r] = container[l]
199:             r -= 1
200:           end
201:         end
202:         container[l] = pivot
203:         top[i+1] = l + 1
204:         bottom[i+1] = bottom[i]
205:         bottom[i] = l
206:         i += 1
207:       else
208:         i -= 1
209:       end
210:     end
211:     container    
212:   end
selection_sort (container)

Selection sort: A naive sort that goes through the container and selects the smallest element, putting it at the beginning. Repeat until the end is reached. Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should be implemented for the container. Time Complexity: О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes

Algorithms::Sort.selection_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
[show source]
    # File lib/algorithms/sort.rb, line 67
67:   def self.selection_sort(container)
68:     0.upto(container.size-1) do |i|
69:       min = i
70:       (i+1).upto(container.size-1) do |j|
71:         min = j if (container[j] <=> container[min]) == -1
72:       end
73:       container[i], container[min] = container[min], container[i] # Swap
74:     end
75:     container
76:   end
shell_sort (container)

Shell sort: Similar approach as insertion sort but slightly better. Requirements: Needs to be able to compare elements with <=>, and the [] []= methods should be implemented for the container. Time Complexity: О(n^2) Space Complexity: О(n) total, O(1) auxiliary Stable: Yes

Algorithms::Sort.shell_sort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
[show source]
     # File lib/algorithms/sort.rb, line 122
122:   def self.shell_sort(container)
123:     increment = container.size/2
124:     while increment > 0 do
125:       (increment..container.size-1).each do |i|
126:         temp = container[i]
127:         j = i
128:         while j >= increment && container[j - increment] > temp do
129:           container[j] = container[j-increment]
130:           j -= increment
131:         end
132:         container[j] = temp
133:       end
134:       increment = (increment == 2 ? 1 : (increment / 2.2).round)
135:     end
136:     container
137:   end