Hello, curious learners! Today, we will embark on a journey through the Quick Sort world. Picture yourself organizing various items — like toys or books — by size or color. That's what Quick Sort does with spectacular speed. Are you ready to explore further? Fantastic! Let's get started.

Quick Sort is a clever algorithm invented by a British computer scientist named Tony Hoare in 1959. It uses a strategy called divide-and-conquer to put elements in order. Quick Sort takes an array, selects a particular pivot element, and then places everything smaller than the pivot on one side and everything larger on the other.

Quick Sort has a three-step process:

1. Pick a random pivot element from the array.
2. Move all elements smaller than the pivot to one side and bigger ones to the other. This operation effectively divides the array into two parts, guaranteeing that all the elements will be kept within their part until the end of the sorting process.
3. Repeat steps 1 and 2 for each part until there are no more unsorted elements.

Let's say we have nine marbles with the numbers [3, 9, 4, 7, 5, 1, 6, 2, 8]. We choose a marble, called the pivot, to help us sort the others. For this example, let's pick 7 as the pivot. After the first round of sorting, we rearrange the marbles so that all marbles smaller than 7 are on the left, and all marbles larger than 7 are on the right. The result would look like this: [3, 4, 5, 1, 6, 2, 7, 9, 8].

At first, this might seem like a small change, but notice that the pivot (7) is now in its correct position in the sorted array. The important part is that now we can treat the left side [3, 4, 5, 1, 6, 2] and the right side [9, 8] as separate arrays. These arrays will never change or mix again, because the pivot is already in its right place.

Let's translate these steps into a concrete Ruby program. We'll tackle it part by part. Our first step is to partition an array around a pivot. In Ruby, we define a method, let's call it partition, to handle this:

Ruby
Copy to clipboard
1def partition(arr, start, end_index)
2  pivot = arr[end_index] # choosing the last element as the pivot
3  i = start - 1  # marking the index of the smaller element
4
5  (start...end_index).each do |j|
6    # checking if the current element is smaller than the pivot
7    if arr[j] <= pivot
8      i += 1
9      # swap arr[i] and arr[j]
10      arr[i], arr[j] = arr[j], arr[i]
11    end
12  end

In this segment of code, we selected the last element as the pivot and placed smaller elements on the left.

The function starts by initializing i to one index before start. i keeps track of the latest position where an element was swapped because it was less than or equal to the pivot. If arr[j] is less than or equal to the pivot, i is incremented, and then arr[j] is swapped with arr[i]. Thus, smaller elements get pushed toward the front of the array (or the given part of the array).

After partitioning, we still need to place the pivot properly in the already partitioned list. We'll add this in the next part of our partition method:

Ruby
Copy to clipboard
1  # Swap arr[i+1] and arr[end_index] (or pivot)
2  arr[i + 1], arr[end_index] = arr[end_index], arr[i + 1]
3
4  i + 1 # return the partition point
5end

Now our partition method is complete! It partitions the array around the pivot and ensures it is in its correct position.

Next up is the quick_sort method. It will use our partition method to sort the left and right portions of the array recursively. Let's code that step-by-step. First, it should call the partitioning process:

Ruby
Copy to clipboard
1def quick_sort(arr, start, end_index)
2  if start < end_index
3    pivot_index = partition(arr, start, end_index)
4    # Ready to split!
5  end
6end

This function has yet to do much, but it's a strong start. We've managed to partition our list around a pivot point.

We must teach our quick_sort method to keep sorting smaller and larger partitions. We do this by simply calling itself recursively for these partitions:

Ruby
Copy to clipboard
1def quick_sort(arr, start, end_index)
2  if start < end_index
3    pivot_index = partition(arr, start, end_index)
4    quick_sort(arr, start, pivot_index - 1) # sort left part
5    quick_sort(arr, pivot_index + 1, end_index) # sort right part
6  end
7end

And that's it! Our Quick Sort implementation is complete. It initially partitions the array and then continues sorting each partition until everything is sorted.

The efficiency or "time complexity" of Quick Sort varies. When sorting items, usually the more unique items, the quicker it is. In the "best" and "average" situations, Quick Sort works like a charm with a time complexity of O(n * log(n)). However, in the "worst" situation, where many items are the same (like a pile of identical blocks), it may take more time, resulting in a time complexity of O(n^2).

Great job! We've untangled the concept of Quick Sort, broken it down piece by piece, and implemented it in Ruby. Now comes the fun part: we will reinforce what you've learned with practical exercises. Ready to dive in?