Tag: quick-sort

Imagine sorting a room full of toys by color. Instead of meticulously comparing each toy, Quick Sort picks one (the “pivot”) and throws it like a ball, creating partitions based on colors “faster than light.” That’s the essence of Quick Sort, partitioning and conquering data with speed and a hint of playful chaos.

Process

Quick Sort, true to its name, lives up to its reputation for speed. But unlike a chaotic mess, its efficiency lies in a well-defined strategy: partitioning and conquering. Let’s delve into the steps of this whirlwind sorting dance:

1. Choose a Pivot: Imagine the data as a group of people waiting in line. Quick Sort picks one person (the pivot) and positions them somewhere in the line. This pivot isn’t random; it can be the first, last, or even a median element.

2. Partition the Line: Now comes the magic! Quick Sort iterates through the line, comparing each person to the pivot. Those shorter than the pivot move to one side, and those taller move to the other. Essentially, the line gets divided into two sections based on the pivot’s height.

3. Conquer and Repeat: But wait, the line isn’t sorted yet! Both the shorter and taller groups, though smaller now, might still be unsorted. So, Quick Sort recursively applies the same “choose-pivot-partition” strategy to each group, further dividing and conquering until each group has only one person (sorted!).

4. Merge and Conquer: Finally, when all groups have just one person (sorted!), Quick Sort meticulously merges them back together in the correct order, ensuring the entire line is now sorted from shortest to tallest (or vice versa, depending on how you define “shorter”).

Pseudo Code

function quickSort(array, start, end):
  # Base case: sub-array with 0 or 1 element is already sorted
  if start >= end:
    return

  # Choose a pivot element (e.g., last element)
  pivot = array[end]

  # Partition the array around the pivot
  partitionIndex = partition(array, start, end, pivot)

  # Recursively sort the sub-arrays before and after the partition
  quickSort(array, start, partitionIndex - 1)
  quickSort(array, partitionIndex + 1, end)

function partition(array, start, end, pivot):
  # Initialize index variables
  i = start - 1
  for j in range(start, end):
    if array[j] <= pivot:
      i += 1
      # Swap elements at i and j
      swap(array[i], array[j])
  # Swap pivot element with element at i + 1 (now the partition index)
  swap(array[i + 1], array[end])
  return i + 1

function swap(a, b):
  # Swap the values of elements a and b
  temp = a
  a = b
  b = temp

Implementation