Quick Sort in Ruby

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:

def partition(arr, start, end_index)
  pivot = arr[end_index] # choosing the last element as the pivot
  i = start - 1  # marking the index of the smaller element

  (start...end_index).each do |j|
    # checking if the current element is smaller than the pivot
    if arr[j] <= pivot
      i += 1
      # swap arr[i] and arr[j]
      arr[i], arr[j] = arr[j], arr[i]
    end
  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).