Sorting Algorithms in Practice

Welcome to this practice-focused lesson on Simple Sorting Algorithms. Sorting is one of the most studied areas in computer science, as it becomes increasingly important with larger datasets. In this unit, we’ll revisit three fundamental sorting algorithms: Bubble, Selection, and Insertion sorts.

These algorithms are excellent for building problem-solving skills and lay the groundwork for understanding more advanced techniques.

In this lesson we'll take a look at QuickSort.

QuickSort is a widely used and efficient sorting algorithm that follows a divide-and-conquer approach. It works by selecting a pivot element and partitioning the array into three parts: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. QuickSort is then applied recursively to the smaller partitions, gradually sorting the entire array.

Here’s an implementation of QuickSort in Ruby:

def quicksort(array)
  # Base case: Return the array if it has 1 or 0 elements.
  return array if array.length <= 1

  # Choose a random pivot.
  pivot = array[rand(array.length)]

  # Partition the array into three parts: less than, equal to, and greater than the pivot.
  left = []
  equal = []
  right = []

  # Classify each element into one of the three parts.
  array.each do |x|
    if x < pivot
      left << x
    elsif x == pivot
      equal << x
    else
      right << x
    end
  end

  # Recursively sort and combine the parts.
  quicksort(left) + equal + quicksort(right)
end

Here's a quick overview on how QuickSort works:

1. Base Case: If the array contains one or zero elements, it is already sorted, and the recursion stops.
2. Pivot Selection: A pivot element is chosen randomly from the array. This pivot acts as a reference point for the partitioning process.
3. Partitioning: The array is divided into three groups:
   • left: Elements less than the pivot.
   • equal: Elements equal to the pivot.
   • right: Elements greater than the pivot.
4. Recursive Sorting: The left and right partitions are sorted recursively using the same method.
5. Combining Results: The sorted left partition, followed by the equal group, and then the sorted right partition, are concatenated to form the fully sorted array.

QuickSort is efficient because its divide-and-conquer strategy reduces the problem size at each step. In the average case, the time complexity is (O(n \log n)). However, if the pivot selection is poor—leading to unbalanced partitions—the worst-case complexity can degrade to (O(n^2)). Ensuring a good pivot selection improves its performance and maintains balance in the partitioning.