Class: Sortech::Sort

Inherits:
Object
  • Object
show all
Defined in:
lib/sortech.rb

Class Method Summary collapse

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.

Parameters:

  • (Array<Integer>)

Returns:

  • Array



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

Parameters:

  • (Array<Integer>)

Returns:

  • Array



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.

Parameters:

  • (Array<Integer>)

Returns:

  • Array



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]

Parameters:

  • (Array<Integer>)

Returns:

  • Array



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

Parameters:

  • (Array<Integer>)

Returns:

  • Array



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.

Parameters:

  • (Array<Integer>)

Returns:

  • Array



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