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:

Ruby
Copy to clipboard
1def quicksort(array)
2  # Base case: Return the array if it has 1 or 0 elements.
3  return array if array.length <= 1
4
5  # Choose a random pivot.
6  pivot = array[rand(array.length)]
7
8  # Partition the array into three parts: less than, equal to, and greater than the pivot.
9  left = []
10  equal = []
11  right = []
12
13  # Classify each element into one of the three parts.
14  array.each do |x|
15    if x < pivot
16      left << x
17    elsif x == pivot
18      equal << x
19    else
20      right << x
21    end
22  end
23
24  # Recursively sort and combine the parts.
25  quicksort(left) + equal + quicksort(right)
26end

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.

Before diving deeper into advanced algorithms like QuickSort, in the Practice section we’ll revisit the simple sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort. These fundamental methods will solidify your understanding of sorting principles and prepare you to tackle more complex techniques.

Let’s dive into practice and sort things out—happy learning!