C++ • SORTING ALGORITHM Quick Sort

C++ • SORTING ALGORITHM

Quick Sort

ALGORITHM

Quick Sort

TIME COMPLEXITY

O(n log n)

SPACE COMPLEXITY

O(log n)

ORDER

Ascending

C++ Implementation

quick_sort.cpp

#include <iostream>
using namespace std;

class ArraySort
{
    int n;
    int a[100];

    // Partition function to place pivot at correct position
    int partition(int low, int high)
    {
        int pivot = a[high];
        int i = (low - 1);

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

    // Helper recursive function for Quick Sort
    void quickSortHelper(int low, int high)
    {
        if (low < high)
        {
            int pi = partition(low, high);
            quickSortHelper(low, pi - 1);
            quickSortHelper(pi + 1, high);
        }
    }

public:

    // Constructor
    ArraySort()
    {
        n = 0;
    }

    // Input function
    void input()
    {
        cout << "Enter length of array: ";
        cin >> n;

        cout << "Enter array elements: ";

        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }

    // Quick Sort interface function
    void quickSort()
    {
        quickSortHelper(0, n - 1);
    }

    // Output function
    void output()
    {
        cout << "Sorted Array: ";

        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
    }
};

int main()
{
    ArraySort obj;

    obj.input();
    obj.quickSort();
    obj.output();

    return 0;
}

Sample Input

Enter length of array: 5
Enter array elements:
5 3 4 1 2

Output

Sorted Array:
1 2 3 4 5

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

class ArraySort

Creates a class named ArraySort containing the array and sorting methods.

int n;

Stores the total number of elements in the array.

int a[100];

Declares an integer array capable of holding up to 100 elements.

int partition(int low, int high)

Picks a pivot element and rearranges the array so smaller elements go left and larger elements go right.

void quickSortHelper(...)

Recursively applies the partition logic to the left and right sub-arrays.

ArraySort()

Class constructor that initializes object properties when instantiated.

n = 0;

Initializes the array size variable to zero.

void input()

Reads the array size and elements from the user.

void quickSort()

Public interface function that initiates recursive sorting from index 0 to n - 1.

void output()

Displays the final sorted array to the console.

ArraySort obj;

Instantiates the ArraySort object and triggers the constructor.

return 0;

Signals successful program execution.

How quick sort works: Quick Sort is a Divide and Conquer algorithm. It picks an element as a pivot (in this case, the last element) and partitions the given array around the picked pivot by placing all smaller elements before it and all larger elements after it. This process is then recursively repeated on the sub-arrays.