class Sortech::Sort

Public Class Methods

bubble(arr) click to toggle source

Sort an array using Bubble sort technique Advantages:

1. Straightforward, simple and slow.
2. Stable.
3. Inefficient on large tables.

@param [Array<Integer>]

@return Array

# 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) click to toggle source

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

@param [Array<Integer>]

@return Array

# 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) click to toggle source

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.

@param [Array<Integer>]

@return Array

# 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) click to toggle source

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>]

@param [Array<Integer>]

@return Array

# 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) click to toggle source

Sort an array using Radix sort technique Advantages:

1. Stable, fast.
2. Used in special cases when the key can be

@param [Array<Integer>]

@return Array TODO: Implement

# File lib/sortech.rb, line 135
def radix(arr)
end
selection(arr) click to toggle source

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.

@param [Array<Integer>]

@return Array

# 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

Private Class Methods

is_sorted?(arr) click to toggle source

Returns true or false depending on whether array is sorted or not

@param [Array<Integer>]

@return Boolean

# File lib/sortech.rb, line 145
def is_sorted? arr
  return false if arr.nil?
  for i in 0..(arr.length - 2)
    if arr[i] > arr[i+1]
      return false
    end
  end
  true
end
merge(arr, left, middle, right) click to toggle source

Splits the array into two halves and merge them in sorted order back to the original array

@param [Array<Integer>, Integer, Integer, Integer]

@return Boolean

# File lib/sortech.rb, line 176
def merge arr, left, middle, right
  n1 = middle - left + 1
  n2 = right - middle

  # Create empty arrays of size n1 and n2
  left_array = Array.new(n1){0}
  right_array = Array.new(n1){0}

  # copy data to empty arrays
  for i in 0..n1
    left_array[i] = arr[left+i]
  end
  for i in 0..n2
    right_array[i] = arr[middle + i + 1]
  end

  # Merge two arrays back into arr
  i = 0
  j = 0
  k = left

  while i < n1 && j < n2
    if left_array[i] <= right_array[j]
      arr[k] = left_array[i]
      i += 1
    else
      arr[k] = right_array[j]
      j += 1
    end
    k += 1
  end

  # copy the remaining elements of left_array, if any
  while i < n1
    arr[k] = left_array[i]
    i += 1
    k += 1
  end

  # copy the remaining elements of right_array, if any
  while j < n2
    arr[k] = right_array[j]
    j += 1
    k += 1
  end
end
partition(arr, low, high) click to toggle source
# File lib/sortech.rb, line 155
def partition arr, low, high
  pivot = arr[high]
  i = low - 1
  for j in low..high-1
    if arr[j] <= pivot
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
    end
  end
  arr[i+1], arr[high] = arr[high], arr[i+1]
  i+1
end