Sorting Algorithms with Ruby

Sorting algorithms are algorithms that put elements of a list or array in a particular order. There are various sorting algorithms, each with their own advantages and disadvantages in terms of time and space complexity. Here are some of the most common sorting algorithms:

1. Bubble Sort: Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

2. Selection Sort: Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places it at the beginning of the list.

3. Insertion Sort: Insertion sort is a sorting algorithm that builds the final sorted list one item at a time. It iterates through an input array and removes one element per iteration, finds the location it belongs within the sorted list, and inserts it there.

4. Merge Sort: Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts each half, and then merges the two sorted halves.

5. Quick Sort: Quick sort is a divide and conquer algorithm that selects a "pivot" element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. It then recursively sorts the sub-arrays.

6. Heap Sort: Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. First, it builds a heap from the input data, and then it repeatedly extracts the maximum element from the heap, which results in a sorted array.

7. Radix Sort: Radix Sort is a sorting algorithm that sorts data by digit positions. It sorts the data by comparing digits in the same position from each item to be sorted.

Each of these algorithms has its own time and space complexity and may be more or less suited to different types of data and input sizes. Choosing the appropriate algorithm for a particular use case can be important for performance reasons.

Complexity

Sorting algorithms can be categorized into two main categories, comparison-based sorting algorithms and non-comparison-based sorting algorithms. Comparison-based sorting algorithms compare elements of a list to sort them, whereas non-comparison-based sorting algorithms utilize other techniques such as counting or radix to sort the elements.

Some common comparison-based sorting algorithms include Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort. Bubble Sort and Selection Sort are simple sorting algorithms with a time complexity of O(n^2). Insertion Sort has an average time complexity of O(n^2), but its best-case time complexity is O(n). Merge Sort and Quick Sort are more efficient algorithms with an average time complexity of O(n log n). Heap Sort is a comparison-based sorting algorithm that uses a heap data structure and has an average time complexity of O(n log n).

Non-comparison-based sorting algorithms include Counting Sort and Radix Sort. Counting Sort is a linear sorting algorithm that has an average time complexity of O(n + k), where k is the range of the input. Radix Sort is a non-comparison-based sorting algorithm that sorts elements by their digits. It has an average time complexity of O(d * (n + k)), where d is the maximum number of digits in the input and k is the range of the input.

Bubble sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

def bubble_sort(array)
  n = array.length
  loop do
    swapped = false

    (n-1).times do |i|
      if array[i] > array[i+1]
        array[i], array[i+1] = array[i+1], array[i]
        swapped = true
      end
    end

    break if not swapped
  end

  array
end

Selection sort

Selection sort is an in-place comparison sort algorithm that divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. The algorithm finds the minimum value in the unsorted sublist and swaps it with the leftmost unsorted element, moving the sublist boundaries one element to the right.

def selection_sort(array)
  n = array.length
  for i in 0...n
    min_idx = i
    for j in (i+1)...n
      if array[j] < array[min_idx]
        min_idx = j
      end
    end
    array[i], array[min_idx] = array[min_idx], array[i]
  end

  array
end

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

def insertion_sort(array)
  n = array.length
  for i in 1...n
    key = array[i]
    j = i - 1

    while j >= 0 && array[j] > key
      array[j+1] = array[j]
      j -= 1
    end

    array[j+1] = key
  end

  array
end

Merge sort

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that if two elements have the same value, they will retain their relative order in the sorted sequence.

def merge_sort(array)
  if array.length <= 1
    return array
  end

  mid = array.length / 2
  left = array[0...mid]
  right = array[mid...array.length]

  left = merge_sort(left)
  right = merge_sort(right)

  merge(left, right)
end

def merge(left, right)
  result = []
  while left.length > 0 && right.length > 0
    if left[0] <= right[0]
      result << left.shift
    else
      result << right.shift
    end
  end

  while left.length > 0
    result << left.shift
  end

  while right.length > 0
    result << right.shift
  end

  result
end

Quick sort

Quick Sort is a sorting algorithm that uses the divide-and-conquer technique to sort an array. It is one of the most efficient sorting algorithms with an average time complexity of O(n*log(n)). The basic idea of Quick Sort is to pick a pivot element, partition the array around the pivot, and then recursively sort the left and right subarrays.

Here are the detailed steps to perform Quick Sort:

1. Choose a pivot element from the array. Typically, the pivot element is chosen as the last element in the array.

2. Partition the array into two subarrays: the left subarray contains all elements smaller than the pivot, and the right subarray contains all elements greater than or equal to the pivot.

3. Recursively apply the Quick Sort algorithm to the left and right subarrays.
   

def quicksort(arr)
  return arr if arr.size <= 1

  # Pick the pivot element
  pivot = arr.last

  # Partition the array into two subarrays
  left = []
  right = []
  arr[0...-1].each do |x|
    if x < pivot
      left << x
    else
      right << x
    end
  end

  # Recursively apply quicksort to the left and right subarrays
  return quicksort(left) + [pivot] + quicksort(right)
end

# Example usage
arr = [7, 2, 9, 4, 1, 8, 5, 6, 3]
sorted_arr = quicksort(arr)
puts sorted_arr.inspect
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

In the above code, the quicksort function takes an array arr as input and returns a sorted array. If the array size is less than or equal to 1, it returns the input array as it is. Otherwise, it picks the last element in the array as the pivot, partitions the array into two subarrays using the pivot, and then recursively applies the Quick Sort algorithm to the left and right subarrays. Finally, it concatenates the sorted left subarray, pivot, and sorted right subarray, and returns the sorted array.

Heap sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a heap from the input data and then repeatedly extracts the maximum element from the heap, which results in a sorted array. The time complexity of Heap Sort is O(n*log(n)).

Here are the detailed steps to perform Heap Sort:

1. Build a max heap from the input array. A max heap is a binary tree where the value of each parent node is greater than or equal to the values of its children.

2. Extract the maximum element from the heap and place it at the end of the array.

3. Heapify the remaining elements of the heap.

4. Repeat steps 2 and 3 until the heap is empty.
   

def heapsort(arr)
  n = arr.length

  # Build a max heap from the input array
  ((n / 2) - 1).downto(0) do |i|
    heapify(arr, n, i)
  end

  # Extract the maximum element from the heap and place it at the end of the array
  (n - 1).downto(1) do |i|
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)
  end

  return arr
end

# Heapify a subtree rooted with node i, which is an index in arr. n is the size of the heap
def heapify(arr, n, i)
  largest = i
  l = (2 * i) + 1
  r = (2 * i) + 2

  if l < n && arr[l] > arr[largest]
    largest = l
  end

  if r < n && arr[r] > arr[largest]
    largest = r
  end

  if largest != i
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)
  end
end

# Example usage
arr = [7, 2, 9, 4, 1, 8, 5, 6, 3]
sorted_arr = heapsort(arr)
puts sorted_arr.inspect
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

In the above code, the heapsort function takes an array arr as input and returns a sorted array using Heap Sort. It first builds a max heap from the input array using the heapify function. The heapify function takes an array arr, the size of the heap n, and an index i as input and heapifies a subtree rooted with node i. It then repeatedly extracts the maximum element from the heap and places it at the end of the array, and then heapifies the remaining elements of the heap. Finally, it returns the sorted array.

Radix sort

Radix Sort is a sorting algorithm that sorts data by digit positions. It sorts the data by comparing digits in the same position from each item to be sorted. Radix Sort is usually used to sort numbers, but it can also be used to sort strings or other data types that can be sorted by their individual characters.

Here are the detailed steps to perform Radix Sort:

1. Find the maximum number in the input array and count the number of digits in it.

2. Starting from the least significant digit (rightmost), sort the input array using counting sort.

3. Move to the next digit (towards the left) and sort the input array again using counting sort.

4. Repeat step 3 until all digits have been sorted.
   

def radixsort(arr)
  max_value = arr.max
  num_digits = Math.log10(max_value).to_i + 1

  num_digits.times do |d|
    counting_sort(arr, d)
  end

  arr
end

# Sort the input array by digit d using counting sort
def counting_sort(arr, d)
  n = arr.length
  counts = Array.new(10, 0)
  output = Array.new(n)

  # Count the number of occurrences of each digit in arr
  arr.each do |x|
    digit = (x / (10 ** d)) % 10
    counts[digit] += 1
  end

  # Modify counts to contain the number of elements less than or equal to each digit
  (1...10).each do |i|
    counts[i] += counts[i - 1]
  end

  # Build the output array by placing each element in its correct sorted position
  (n - 1).downto(0) do |i|
    x = arr[i]
    digit = (x / (10 ** d)) % 10
    output[counts[digit] - 1] = x
    counts[digit] -= 1
  end

  # Copy the output array back to the input array
  arr.each_index do |i|
    arr[i] = output[i]
  end
end

# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radixsort(arr)
puts sorted_arr.inspect
# Output: [2, 24, 45, 66, 75, 90, 170, 802]

In the above code, the radixsort function takes an array arr as input and returns a sorted array using Radix Sort. It first finds the maximum value in the input array and counts the number of digits in it. It then sorts the input array by digit positions starting from the least significant digit using the counting_sort function. The counting_sort function takes an array arr and a digit position d as input and sorts the input array by digit d using counting sort. Finally, it returns the sorted array.

Conclusion

In conclusion, sorting algorithms are an essential part of computer science and are used extensively in a wide range of applications. There are many different types of sorting algorithms, each with their strengths and weaknesses, which make them suited for different use cases. Some algorithms like Quick Sort are generally faster than others, while others like Radix Sort are specialized for certain types of data.

It's important to choose the right sorting algorithm for the job and to understand the performance characteristics of each algorithm. The time and space complexity of a sorting algorithm are important factors to consider when choosing an algorithm for a particular task. Additionally, some sorting algorithms like Merge Sort and Heap Sort are stable, meaning that they preserve the relative order of equal elements in the input array, while others like Quick Sort are not.

Overall, a good understanding of sorting algorithms is an important tool in a programmer's toolbox, and choosing the right algorithm for a given task can have a significant impact on the performance of an application.