Quick Sort Algorithm in DSA C++ - Build from Scratch

Quick Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers quickly. Sorting helps organize data so you can find things faster, like arranging books by their titles on a shelf.

🎯 Goal: Build a program that uses the Quick Sort algorithm to sort an array of integers in ascending order.

📋 What You'll Learn

Create an array called arr with the exact integers: 29, 10, 14, 37, 13

Create an integer variable n that stores the size of the array

Write a function partition that helps divide the array around a pivot

Write a recursive function quickSort that sorts the array using the partition function

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Quick Sort is used in many software applications to organize data quickly, such as sorting search results or arranging files.

💼 Career

Understanding Quick Sort helps in technical interviews and improves problem-solving skills for software development roles.

1

Create the array and its size

Create an integer array called arr with these exact values: 29, 10, 14, 37, 13. Then create an integer variable n and set it to the size of arr.

DSA C++

int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr) / sizeof(arr[0]);
// Your code here

Hint

Use sizeof(arr) / sizeof(arr[0]) to find the number of elements in the array.

2

Write the partition function

Write a function called partition that takes an integer array arr, two integers low and high. Use the last element as pivot, rearrange elements so smaller ones come before pivot, and return the pivot's final index.

DSA C++

int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr) / sizeof(arr[0]);

int partition(int arr[], int low, int high) {
    // Your code here
}

Hint

The pivot is the last element arr[high]. Use a loop from low to high - 1 to compare and swap elements.

3

Write the quickSort function

Write a recursive function called quickSort that takes an integer array arr, two integers low and high. If low is less than high, call partition to get pivot index, then recursively sort the parts before and after the pivot.

DSA C++

int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr) / sizeof(arr[0]);

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    // Your code here
}

Hint

Use the pivot index from partition to split the array and call quickSort on each part.

4

Print the sorted array

Call quickSort with arr, 0, and n - 1 to sort the array. Then print the sorted array elements separated by spaces on one line.

DSA C++

int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr) / sizeof(arr[0]);

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Hint

Call quickSort(arr, 0, n - 1) to sort. Use a loop to print each element followed by a space.