Quick Sort in Ascending Order in C++

1. Introduction

In this blog post, we will learn how to write a C++ program to sort an array of integers in Ascending Order using the Quick Sort algorithm.

Quick Sort is a 'divide and conquer' algorithm. The primary concept behind Quick Sort is to pick a 'pivot' element from the array and partition 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.

2. Program Overview

1. partition(): Function that takes an element as a pivot, places the pivot at its correct position, and places all elements smaller to the left and all greater elements to the right.

2. quickSort(): The main recursive function that implements QuickSort.

3. printArray(): Utility function to display the array's elements.

4. main(): The main function that starts the program.

3. Code Program

#include<iostream>
using namespace std;

// This function takes last element as pivot, places it at its correct position,
// and places all smaller (smaller than pivot) to the left and all greater elements to the right
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++; // increment index of smaller element
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// Main function that sorts arr[low..high] using quickSort
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);
    }
}

// Utility function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array is: \n";
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    cout << "Sorted array in ascending order is: \n";
    printArray(arr, n);
    return 0;
}

Output:

Original array is:
10 7 8 9 1 5 
Sorted array in ascending order is: 
1 5 7 8 9 10 

4. Step By Step Explanation

1. partition(): The goal of this function is to select a pivot, in this case, the last element of the array, and to place it in the right position such that all numbers less than the pivot are on the left and all numbers greater than the pivot are on the right. This function returns the index of the pivot element.

2. quickSort(): This is the main function that recursively sorts the elements of the array. Based on the index returned from the partition, it recursively sorts the left and right segments of the array.

3. printArray(): A utility function to display the array elements. This helps visualize the array before and after sorting.

4. main(): This function initializes a sample array, displays its elements, calls the quickSort function to sort the array, and then displays the sorted elements.

The partition() function is the essence of the Quick Sort. The choice of pivot and the partition logic are critical to the efficiency of the Quick Sort algorithm.

Related C++ Programs on Sorting Algorithms

• Bubble Sort in Ascending Order in C++
• Bubble Sort in Descending Order in C++
• Selection Sort in Ascending Order in C++
• Selection Sort in Descending Order in C++
• Insertion Sort in Ascending Order in C++
• Insertion Sort in Descending Order in C++
• Merge Sort in Ascending Order in C++
• Merge Sort in Descending Order in C++
• Quick Sort in Ascending Order in C++
• Quick Sort in Descending Order in C++
• Heap Sort in Ascending Order in C++
• Heap Sort in Descending Order in C++