Class: Sortech::Sort
- Inherits:
-
Object
- Object
- Sortech::Sort
- Defined in:
- lib/sortech.rb
Class Method Summary collapse
-
.bubble(arr) ⇒ Object
Sort an array using Bubble sort technique Advantages: 1.
-
.insertion(arr) ⇒ Object
Sort an array using Insertion sort technique.
-
.mergesort(arr, left = 0, right = arr.length-1) ⇒ Object
Sort an array using Merge sort technique Advantages: 1.
-
.quicksort(arr, low = 0, high = arr.length-1) ⇒ Object
Sort an array using Quick sort technique Advantages: 1.
-
.radix(arr) ⇒ Object
Sort an array using Radix sort technique Advantages: 1.
-
.selection(arr) ⇒ Object
Sort an array using Selection sort technique Advantages: 1.
Class Method Details
.bubble(arr) ⇒ Object
Sort an array using Bubble sort technique Advantages:
1. Straightforward, simple and slow.
2. Stable.
3. Inefficient on large tables.
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
# File 'lib/sortech.rb', line 14 def bubble(arr) arr if arr.length == 0 || is_sorted?(arr) n = arr.length loop do flag = false for i in 0..n - 2 if arr[i] > arr[i+1] arr[i], arr[i+1] = arr[i+1], arr[i] flag = true end end n -= 1 break unless flag end arr end |
.insertion(arr) ⇒ Object
Sort an array using Insertion sort technique
Advantages:
1. Efficient for small list and mostly sorted list.
2. Sort big array slowly.
3. Save memory
69 70 71 72 73 74 75 76 77 78 79 80 |
# File 'lib/sortech.rb', line 69 def insertion(arr) for i in 1..arr.length - 1 t = arr[i] j = i - 1 while j >= 0 && arr[j] > t arr[j+1] = arr[j] j -= 1 end arr[j+1] = t end arr end |
.mergesort(arr, left = 0, right = arr.length-1) ⇒ Object
Sort an array using Merge sort technique Advantages:
1. Well for very large list, stable sort.
2. A fast recursive sorting.
3. Both useful for internal and external sorting.
4. It requires an auxiliary array that is as large as the original array to be sorted.
114 115 116 117 118 119 120 121 122 123 124 |
# File 'lib/sortech.rb', line 114 def mergesort(arr, left=0,right=arr.length-1) if left < right middle = (left + (right - 1))/2 mergesort(arr,left,middle) # sort first half mergesort(arr, middle+1,right) # sort second half merge(arr, left, middle, right) # merge the two arrays end arr end |
.quicksort(arr, low = 0, high = arr.length-1) ⇒ Object
Sort an array using Quick sort technique Advantages:
1. Fastest sorting algorithm in practice.
2. Available in many standard libraries.
3. O (log n) space usage.
4. Unstable sort and complex for choosing a good pivot element. # @param [Array<Integer>]
93 94 95 96 97 98 99 100 101 |
# File 'lib/sortech.rb', line 93 def quicksort(arr, low=0, high=arr.length-1) if low < high pi = partition(arr, low, high) quicksort(arr, low, pi-1) # called before pi quicksort(arr, pi+1, high) # called after pi end arr end |
.radix(arr) ⇒ Object
Sort an array using Radix sort technique Advantages:
1. Stable, fast.
2. Used in special cases when the key can be
TODO: Implement
135 136 |
# File 'lib/sortech.rb', line 135 def radix(arr) end |
.selection(arr) ⇒ Object
Sort an array using Selection sort technique Advantages:
1. Improves the performance of bubble sort and also slow.
2. Unstable but can be implemented as a stable sort.
3. Quite slow for large amount of data.
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# File 'lib/sortech.rb', line 41 def selection(arr) arr if arr.length == 0 || is_sorted?(arr) n = arr.length for i in 0..n - 1 s = arr[i] p = i for j in i+1..n - 1 if s > arr[j] s = arr[j] p = j end end arr[i], arr[p] = arr[p], arr[i] end arr end |