Quick Sort | DSA in C++ - Software Development PDF Download

Introduction

Sorting is a fundamental operation in computer science, and one of the commonly used sorting algorithms is Quick Sort. It is an efficient and widely adopted algorithm for sorting elements in an array. In this article, we will explore Quick Sort in DSA (Data Structures and Algorithms) using C++. We'll cover the basic concept, step-by-step implementation, and provide multiple examples to help you understand the algorithm better. So, let's get started!

Understanding Quick Sort

• Quick Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
• The sub-arrays are then recursively sorted independently. Finally, the sub-arrays are combined to obtain a sorted array.
• The key steps involved in Quick Sort are:
  • Choosing a pivot element.
  • Partitioning the array based on the pivot.
  • Recursively applying Quick Sort on the sub-arrays.

Step-by-Step Implementation

Let's walk through the implementation of Quick Sort in C++ step by step.

Step 1: Choosing the Pivot

• We need to choose a pivot element from the array. The choice of pivot can affect the performance of the algorithm.
• For simplicity, we'll choose the rightmost element of the array as the pivot in our examples.

Step 2: Partitioning the Array

• We'll partition the array based on the pivot, such that all elements less than the pivot come before it, and all elements greater than the pivot come after it.
• We'll use two pointers, 'i' and 'j,' to keep track of the partitioning process. 'i' starts from the leftmost element, and 'j' moves towards the right.
• Elements smaller than the pivot are swapped with the element at index 'i' (initially set to the leftmost element), and 'i' is incremented.
• After the loop ends, we swap the pivot element with the element at index 'i' to place it at its correct position.

Step 3: Recursive Sorting

• Once we have the pivot in its correct position, we recursively apply Quick Sort on the sub-arrays before and after the pivot element.
• This process continues until the sub-arrays contain only one element or are empty, as a single element or an empty array is considered sorted.

Quick Sort Implementation in C++

Let's take a look at the C++ code implementation of Quick Sort:

#include <iostream>

// Function to swap two elements

void swap(int* a, int* b) {

    int temp = *a;

    *a = *b;

    *b = temp;

}

// Partitioning the array and returning the pivot index

int partition(int arr[], int low, int high) {

    int pivot = arr[high]; // Choosing the pivot as the rightmost element

    int i = (low - 1);

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

        if (arr[j] < pivot) {

            i++;

            swap(&arr[i], &arr[j]);

        }

    }

    swap(&arr[i + 1], &arr[high]);

    return (i + 1);

}

// Quick Sort implementation

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pivotIndex = partition(arr, low, high);

        quickSort(arr, low, pivotIndex - 1);

        quickSort(arr, pivotIndex + 1, high);

    }

}

// Function to print an array

void printArray(int arr[], int size) {

    for (int i = 0; i < size; i++)

        std::cout << arr[i] << " ";

    std::cout << std::endl;

}

int main() {

    int arr[] = {10, 7, 8, 9, 1, 5};

    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original Array: ";

    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    std::cout << "Sorted Array: ";

    printArray(arr, n);

    return 0;

}

Explanation:

• The code starts by defining a 'swap' function that takes two pointers and swaps the values they point to.
• The 'partition' function takes the array, a lower index, and a higher index as parameters.
• Inside the 'partition' function, the pivot is chosen as the rightmost element ('arr[high]').
• The variable 'i' is initialized as 'low - 1' to keep track of the smaller elements.
• The loop iterates from 'low' to 'high-1'. If an element is smaller than the pivot, 'i' is incremented, and the current element is swapped with the element at index 'i'.
• After the loop ends, the pivot element is swapped with the element at index 'i + 1' to place it at its correct position. The function then returns the pivot index.
• The 'quickSort' function takes the array, a lower index, and a higher index as parameters.
• Inside the 'quickSort' function, if the lower index is less than the higher index, the partition function is called to get the pivot index.
• Then, the 'quickSort' function is recursively called on the sub-arrays before and after the pivot index.
• Finally, the printArray function is defined to print the elements of the array.

Example Output:

Let's run the code with the example array {10, 7, 8, 9, 1, 5} and see the output:

Original Array: 10 7 8 9 1 5

Sorted Array: 1 5 7 8 9 10

The array is successfully sorted in ascending order using the Quick Sort algorithm.

Sample Problems

Problem 1: Sort the following array using Quick Sort: '{25, 10, 32, 1, 8, 14}'.

The sorted array will be: '{1, 8, 10, 14, 25, 32}'.

Problem 2: Sort the array in descending order using Quick Sort: '{15, 27, 3, 19, 12}'.

The sorted array in descending order will be: '{27, 19, 15, 12, 3}'.

Conclusion

Quick Sort is a powerful sorting algorithm that efficiently sorts elements in an array. In this article, we discussed the basic concept of Quick Sort, provided a step-by-step implementation guide in C++, and demonstrated examples to help you understand the algorithm. Remember to choose a suitable pivot and carefully implement the partitioning process. Quick Sort is widely used in practice due to its simplicity and efficiency.