Module: Algorithms::Sort
- Defined in:
- lib/algorithms/sort.rb
Overview
This module implements sorting algorithms. Documentation is provided for each algorithm.
Class Method Summary collapse
-
.bubble_sort(container) ⇒ Object
Bubble sort: A very naive sort that keeps swapping elements until the container is sorted.
-
.comb_sort(container) ⇒ Object
Comb sort: A variation on bubble sort that dramatically improves performance.
- .dualpivot(container, left = 0, right = container.size-1, div = 3) ⇒ Object
- .dualpivot_swap(container, i, j) ⇒ Object
-
.dualpivotquicksort(container) ⇒ Object
Dual-Pivot Quicksort is a variation of Quicksort by Vladimir Yaroslavskiy.
-
.heapsort(container) ⇒ Object
Heap sort: Uses a heap (implemented by the Containers module) to sort the collection.
-
.insertion_sort(container) ⇒ Object
Insertion sort: Elements are inserted sequentially into the right position.
- .merge(left, right) ⇒ Object
-
.mergesort(container) ⇒ Object
Mergesort: A stable divide-and-conquer sort that sorts small chunks of the container and then merges them together.
-
.partition(data, left, right) ⇒ Object
Quicksort: A divide-and-conquer sort that recursively partitions a container until it is sorted.
-
.quicksort(container) ⇒ Object
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.
-
.selection_sort(container) ⇒ Object
Selection sort: A naive sort that goes through the container and selects the smallest element, putting it at the beginning.
-
.shell_sort(container) ⇒ Object
Shell sort: Similar approach as insertion sort but slightly better.
Class Method Details
.bubble_sort(container) ⇒ Object
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]
16 17 18 19 20 21 22 23 24 25 26 27 28 |
# File 'lib/algorithms/sort.rb', line 16 def self.bubble_sort(container) loop do swapped = false (container.size-1).times do |i| if (container[i] <=> container[i+1]) == 1 container[i], container[i+1] = container[i+1], container[i] # Swap swapped = true end end break unless swapped end container end |
.comb_sort(container) ⇒ Object
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]
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# File 'lib/algorithms/sort.rb', line 39 def self.comb_sort(container) container gap = container.size loop do gap = gap * 10/13 gap = 11 if gap == 9 || gap == 10 gap = 1 if gap < 1 swapped = false (container.size - gap).times do |i| if (container[i] <=> container[i + gap]) == 1 container[i], container[i+gap] = container[i+gap], container[i] # Swap swapped = true end end break if !swapped && gap == 1 end container end |
.dualpivot(container, left = 0, right = container.size-1, div = 3) ⇒ Object
278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 |
# File 'lib/algorithms/sort.rb', line 278 def self.dualpivot(container, left=0, right=container.size-1, div=3) length = right - left if length < 27 # insertion sort for tiny array container.each_with_index do |data,i| j = i - 1 while j >= 0 break if container[j] <= data container[j + 1] = container[j] j = j - 1 end container[j + 1] = data end else # full dual-pivot quicksort third = length / div # medians m1 = left + third m2 = right - third if m1 <= left m1 = left + 1 end if m2 >= right m2 = right - 1 end if container[m1] < container[m2] dualpivot_swap(container, m1, left) dualpivot_swap(container, m2, right) else dualpivot_swap(container, m1, right) dualpivot_swap(container, m2, left) end # pivots pivot1 = container[left] pivot2 = container[right] # pointers less = left + 1 great = right - 1 # sorting k = less while k <= great if container[k] < pivot1 dualpivot_swap(container, k, less += 1) elsif container[k] > pivot2 while k < great && container[great] > pivot2 great -= 1 end dualpivot_swap(container, k, great -= 1) if container[k] < pivot1 dualpivot_swap(container, k, less += 1) end end k += 1 end # swaps dist = great - less if dist < 13 div += 1 end dualpivot_swap(container, less-1, left) dualpivot_swap(container, great+1, right) # subarrays dualpivot(container, left, less-2, div) dualpivot(container, great+2, right, div) # equal elements if dist > length - 13 && pivot1 != pivot2 for k in less..great do if container[k] == pivot1 dualpivot_swap(container, k, less) less += 1 elsif container[k] == pivot2 dualpivot_swap(container, k, great) great -= 1 if container[k] == pivot1 dualpivot_swap(container, k, less) less += 1 end end end end # subarray if pivot1 < pivot2 dualpivot(container, less, great, div) end container end end |
.dualpivot_swap(container, i, j) ⇒ Object
364 365 366 |
# File 'lib/algorithms/sort.rb', line 364 def self.dualpivot_swap(container, i, j) container[i], container[j] = container[j], container[i] end |
.dualpivotquicksort(container) ⇒ Object
Dual-Pivot Quicksort is a variation of Quicksort by Vladimir Yaroslavskiy. This is an implementation of the algorithm as it was found in the original research paper:
iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
Mirror: codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf
“This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.”
-- http://download.oracle.com/javase/7/docs/api/java/util/Arrays.html
The algorithm was improved by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch, and was implemented as the default sort algorithm for primatives in Java 7.
Implementation in the Java JDK as of November, 2011: www.docjar.com/html/api/java/util/DualPivotQuicksort.java.html
It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively. This has been fully examined mathematically and experimentally.
Requirements: Container should implement #pop and include the Enumerable module. Time Complexity: О(n log n) average, О(n log n) worst-case Space Complexity: О(n) auxiliary
Stable: No
Algorithms::Sort.dualpivotquicksort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]
273 274 275 276 |
# File 'lib/algorithms/sort.rb', line 273 def self.dualpivotquicksort(container) return container if container.size <= 1 dualpivot(container, 0, container.size-1, 3) end |
.heapsort(container) ⇒ Object
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]
85 86 87 88 89 90 |
# File 'lib/algorithms/sort.rb', line 85 def self.heapsort(container) heap = Containers::Heap.new(container) ary = [] ary << heap.pop until heap.empty? ary end |
.insertion_sort(container) ⇒ Object
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]
100 101 102 103 104 105 106 107 108 109 110 111 112 |
# File 'lib/algorithms/sort.rb', line 100 def self.insertion_sort(container) return container if container.size < 2 (1..container.size-1).each do |i| value = container[i] j = i-1 while j >= 0 and container[j] > value do container[j+1] = container[j] j = j-1 end container[j+1] = value end container end |
.merge(left, right) ⇒ Object
230 231 232 233 234 235 236 |
# File 'lib/algorithms/sort.rb', line 230 def self.merge(left, right) sorted = [] until left.empty? or right.empty? left.first <= right.first ? sorted << left.shift : sorted << right.shift end sorted + left + right end |
.mergesort(container) ⇒ Object
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]
222 223 224 225 226 227 228 |
# File 'lib/algorithms/sort.rb', line 222 def self.mergesort(container) return container if container.size <= 1 mid = container.size / 2 left = container[0...mid] right = container[mid...container.size] merge(mergesort(left), mergesort(right)) end |
.partition(data, left, right) ⇒ Object
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
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 |
# File 'lib/algorithms/sort.rb', line 154 def self.partition(data, left, right) pivot = data[front] left += 1 while left <= right do if data[frontUnknown] < pivot back += 1 data[frontUnknown], data[back] = data[back], data[frontUnknown] # Swap end frontUnknown += 1 end data[front], data[back] = data[back], data[front] # Swap back end |
.quicksort(container) ⇒ Object
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
180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 |
# File 'lib/algorithms/sort.rb', line 180 def self.quicksort(container) bottom, top = [], [] top[0] = 0 bottom[0] = container.size i = 0 while i >= 0 do l = top[i] r = bottom[i] - 1; if l < r pivot = container[l] while l < r do r -= 1 while (container[r] >= pivot && l < r) if (l < r) container[l] = container[r] l += 1 end l += 1 while (container[l] <= pivot && l < r) if (l < r) container[r] = container[l] r -= 1 end end container[l] = pivot top[i+1] = l + 1 bottom[i+1] = bottom[i] bottom[i] = l i += 1 else i -= 1 end end container end |
.selection_sort(container) ⇒ Object
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]
67 68 69 70 71 72 73 74 75 76 |
# File 'lib/algorithms/sort.rb', line 67 def self.selection_sort(container) 0.upto(container.size-1) do |i| min = i (i+1).upto(container.size-1) do |j| min = j if (container[j] <=> container[min]) == -1 end container[i], container[min] = container[min], container[i] # Swap end container end |
.shell_sort(container) ⇒ Object
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]
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
# File 'lib/algorithms/sort.rb', line 122 def self.shell_sort(container) increment = container.size/2 while increment > 0 do (increment..container.size-1).each do |i| temp = container[i] j = i while j >= increment && container[j - increment] > temp do container[j] = container[j-increment] j -= increment end container[j] = temp end increment = (increment == 2 ? 1 : (increment / 2.2).round) end container end |