Lesson 5
Simple Sorting Algorithms with C++
Lesson Overview

Welcome to the lesson dedicated to Quick Sort. Sorting is one of the most investigated classes of algorithms in computer science. Understanding different methods of sorting becomes more crucial as data sizes increase.

Quick Look at QuickSort

The QuickSort algorithm is designed to sort an unsorted array by employing the Divide and Conquer Technique. The algorithm efficiently achieves this with an average time complexity of O(n log n). The idea behind it is to pick a pivot element from the array and partition the other elements into two arrays according to whether they are less than or greater than the pivot.

Here's an overview of how QuickSort works:

  1. Pivot Selection: Choose a pivot element from the array.

    • The pivot can be any element, but commonly used strategies include picking the first element, the last element, or selecting a random element.

  2. Partitioning the Array: Rearrange the array such that:

    • All elements less than the pivot come before the pivot.
    • All elements greater than the pivot come after the pivot.
    • The pivot element is now in its correct sorted position.

  3. Recursive Sorting:

    • Recursively apply the quickSort function to the subarray of elements with values less than the pivot.
    • Recursively apply the quickSort function to the subarray of elements with values greater than the pivot.
Example:

Given the array [10, 7, 8, 9, 1, 5], let's sort it using QuickSort:

  1. Choose Pivot: Let's pick the last element, 5, as the pivot.

  2. Partition:

    • Elements less than 5: [1]
    • Elements greater than 5: [10, 7, 8, 9]
    • Array after partitioning: [1, 5, 10, 7, 8, 9]

  3. Recursive QuickSort:

    • Apply QuickSort to [1] (Already sorted)
    • Apply QuickSort to [10, 7, 8, 9]

  4. Repeat the process for the subarray [10, 7, 8, 9], choosing pivots, partitioning, and recursing until the entire array is sorted.

This approach ensures that the sorting process is performed efficiently by continually breaking down the problem into smaller subproblems, which are easier to solve.

We will use a helper function: partition.

The implementation of QuickSort is:

C++
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5// Partition function that makes use of pivot
6int partition(std::vector<int>& arr, int low, int high) {
7    int pivot = arr[high]; // pivot
8    int i = (low - 1); // Index of smaller element
9
10    for (int j = low; j < high; j++) {
11        // If the current element is smaller than or equal to the pivot
12        if (arr[j] <= pivot) {
13            i++;
14            std::swap(arr[i], arr[j]);
15        }
16    }
17    std::swap(arr[i + 1], arr[high]);
18    return (i + 1);
19}
20
21// The main function that implements QuickSort
22void quickSort(std::vector<int>& arr, int low, int high) {
23    if (low < high) {
24        // pi is the partitioning index, arr[p] is now at the right place
25        int pi = partition(arr, low, high);
26        // Separately sort elements before partition and after partition
27        quickSort(arr, low, pi - 1);
28        quickSort(arr, pi + 1, high);
29    }
30}
Partition Breakdown

Let's break down the partition function step by step:

Function Definition

This line defines the partition function which returns an integer. The function takes a reference to a vector of integers arr and two integers low and high as its parameters. These specify the subarray to be partitioned.

C++
1int partition(std::vector<int>& arr, int low, int high)

Initialize the Pivot

Select the last element in the subarray (indexed by high) as the pivot. The pivot is the reference value around which the array will be partitioned.

C++
1int pivot = arr[high]; // pivot

Initialize the Partition Index

Initialize i to low - 1. This index keeps track of the boundary between elements smaller than the pivot and not yet positioned elements.

C++
1int i = (low - 1); // Index of smaller element

Iterate Over the Subarray

Use a for loop to iterate over the subarray from the low index to high - 1. This loop will compare each element with the pivot.

C++
1for (int j = low; j < high; j++)

Compare Current Element with Pivot

Inside the loop, check if the current element arr[j] is less than or equal to the pivot.

C++
1if (arr[j] <= pivot)

Swap Elements if Condition is Met

If the current element arr[j] is less than or equal to the pivot:

  • Increment i.
  • Swap the elements at index i and j to move the smaller element to the correct side of the pivot.
C++
1i++;
2std::swap(arr[i], arr[j]);

Place Pivot in Correct Position

After the loop completes, place the pivot element in its correct sorted position by swapping it with the element at i + 1. This guarantees that all elements to the left of the pivot are smaller, and all elements to the right are larger.

C++
1std::swap(arr[i + 1], arr[high]);

Return the Partition Index

Return the partition index, which is i + 1. This index marks the final position of the pivot element.

C++
1return (i + 1);

In summary, the partition function rearranges the elements of the array such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right. The pivot element is placed in its correct sorted position, and the function returns this index, effectively dividing the array into two subarrays around the pivot for further sorting.

Quick Sort Breakdown

Let's break down the quickSort function step by step:

Function Definition

This line defines the quickSort function that returns void. The function takes a reference to a vector of integers arr and two integers low and high as its parameters. These specify the subarray to be sorted. The function does not return anything, but the input arr becomes sorted.

C++
1void quickSort(std::vector<int>& arr, int low, int high)

Base Case: Check if Subarray has More than One Element

The if condition ensures that the subarray has more than one element to sort. If low is not less than high, the function returns without making any changes. This is the base case for the recursion.

C++
1if (low < high)

Partition the Subarray

Call the partition function to rearrange the elements so that all elements less than the pivot are on the left, and all elements greater are on the right. The function returns the index of the pivot element in its correct sorted position.

C++
1int pi = partition(arr, low, high);

Recursively Sort Elements Before the Pivot

Recursively call the quickSort function on the subarray of elements before the pivot index. This ensures that this left subarray gets sorted.

C++
1quickSort(arr, low, pi - 1);

Recursively Sort Elements After the Pivot

Recursively call the quickSort function on the subarray of elements after the pivot index. This ensures that this right subarray gets sorted.

C++
1quickSort(arr, pi + 1, high);

In summary, the quickSort function sorts an array by using a divide-and-conquer strategy. It first partitions the array around a pivot element, placing the pivot in its correct position. Then, it recursively sorts the subarrays formed around the pivot. The base case ensures that subarrays with one or zero elements do not need further sorting, allowing the recursion to terminate.

Practice Time

Great job learning about quick sort! These foundational algorithms will not only reinforce your understanding of the sorting principle but are often used as a stepping stone to understanding more complex algorithms. Happy learning, and let's sort it out!

Enjoy this lesson? Now it's time to practice with Cosmo!
Practice is how you turn knowledge into actual skills.