Quick Sort Implementation In C++

Quick Sort stands out as a widely recognized sorting algorithm celebrated for its time complexity and effectiveness.

History

Tony Hoare introduced the Quick Sort algorithm in 1959 during his research in computer science. This sorting algorithm is highly efficient and commonly employed in various applications.

The origins of Quick Sort can be linked to the exploration of sorting algorithms during the initial stages of computer science. Tony Hoare, an esteemed computer scientist from Britain, created Quick Sort as a superior and more effective option compared to the sorting algorithms that were already in use.

Hoare first created the algorithm in the Algol 60 coding language and released it in his thesis named "Quicksort" in 1961. He explained the algorithm as a divide-and-conquer strategy that utilizes element partitioning to accomplish effective sorting.

Quick Sort became well-known for its simplicity and effectiveness in real-world scenarios. With an average time complexity of O(n log n), it stands out as one of the swiftest sorting algorithms in many situations. Moreover, this algorithm demonstrates excellent performance with extensive data sets and exhibits strong cache efficiency.

Over time, Quick Sort has experienced multiple enhancements and enhancements. Various versions of the algorithm have been suggested, including randomized Quick Sort and Quick Sort with three-way partitioning, to enhance its efficiency and address particular situations.

Today, Quick Sort is commonly employed in real-world scenarios and is frequently the automatic selection for sorting in numerous programming languages and libraries. Its effectiveness, straightforward implementation, and flexibility contribute to its widespread adoption across various use cases.

Implementation of Quick Sort in C++:

#include <iostream>
using namespace std;

// Function to swap two elements
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// Partitioning the array and returning the pivot index
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Choosing the last element as the pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // If the current element is smaller than or equal to the 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);
}

// The main function that implements QuickSort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[p] is now at the right place
        int pi = partition(arr, low, high);

        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Function to print an 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[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: " << endl;
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: " << endl;
    printArray(arr, n);

    return 0;
}

Output:

Original array:
64 25 12 22 11
Sorted array:
11 12 22 25 64

Explanation:

• ✅ The swap function takes two integer pointers a and b as parameters. It swaps the values pointed to by a and b.
• ✅ The partition function takes an array arr, the lower index low, and the higher index high as parameters. It selects the pivot element, which is typically chosen as the last element of the array (arr[high]).
• ✅ The partition function initializes the index of the smaller element (i) to (low - 1).
• ✅ It then iterates through the array from the low index to high - 1 using the variable j. If an element arr[j] is smaller than or equal to the pivot, it increments i by 1 and swaps arr[i] with arr[j].
• ✅ After the loop, the pivot element is placed in its correct position by swapping it with the element at arr[i + 1]. This ensures that all elements smaller than the pivot are on the left side of it, and all elements greater than the pivot are on the right side.
• ✅ The partition function returns the index of the pivot element.
• ✅ The quickSort function is the main recursive function that implements the Quick Sort algorithm. It takes an array arr, the lower index low, and the higher index high as parameters.
• ✅ In the quickSort function, if the low index is less than the high index, it means there is more than one element in the sub-array, and partitioning is required.
• ✅ It calls the partition function to partition the array and get the index of the pivot element.
• ✅ It then recursively calls quickSort for the sub-array before the pivot (i.e., from low to pi - 1) and the sub-array after the pivot (i.e., from pi + 1 to high).
• ✅ The recursion continues until each sub-array contains only one element. At this point, the array is sorted.
• ✅ The printArray function takes an array arr and the size of the array as parameters. It prints the elements of the array.
• ✅ In the main function, an array is initialized with some values. The original array is printed using the printArray function, and then the quickSort function is called to sort the array. Finally, the sorted array is printed again using printArray.

Examples:

Example 1: Quick Sort in C++ using an array of strings:

#include <iostream>
#include <vector>

using namespace std;

// Function to partition the array into two sub-arrays
// and return the index of the pivot element
int partition(vector<string> &arr, int low, int high) {
    string pivot = arr[high]; // Choose the rightmost element as the pivot
    int i = (low - 1);        // Initialize the index of the smaller element

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

    // Swap the pivot element with the element at index i+1
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// Function to perform Quick Sort
void quickSort(vector<string> &arr, int low, int high) {
    if (low < high) {
        // Find pivot such that elements smaller than pivot are on the left
        // and elements greater than pivot are on the right
        int pi = partition(arr, low, high);

        // Recursively sort the elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<string> arr = {"apple", "banana", "cherry", "date", "grape", "fig"};
    int n = arr.size();

    cout << "Original Array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    quickSort(arr, 0, n - 1);

    cout << "Sorted Array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Original Array: apple banana cherry date grape fig 
Sorted Array: apple banana cherry date fig grape

Explanation:

• ✅ Integrate Libraries: The code incorporates libraries for handling input/output operations and utilizing vectors.
• ✅ Partitioning Function:

The function partition accepts a vector of strings, arr, along with two indices, low and high.

It chooses the element at the far right (arr[high]) as the pivot.

It compares every item within the interval [low, high-1] against the pivot.

If a given element is smaller than or equal to the pivot value, it is shifted to the left side of the pivot.

After the iteration, it positions the pivot element correctly, arranging smaller elements to the left and larger elements to the right, then provides the index of the pivot.

• ✅ Implementation of Quick Sort Algorithm:

quickSort organizes a string vector by iteratively choosing pivot points and dividing the array into sections.

It starts with a range defined by low and high.

If low is less than high, it:

Invokes the partition function to determine a pivot index (pi) and partition the array accordingly.

Apply the quickSort algorithm recursively to the sub-arrays on the left and right (preceding and following the pivot element).

• ✅ Main Method:

Creates a string vector named arr, containing elements that are not sorted.

Prints the original array.

Invokes the quickSort function to arrange the elements in the array.

• ✅ Displays the sorted array on the screen.

In this instance, Quick Sort is implemented to arrange a collection of strings. The process involves partitioning and exchanging elements by comparing strings. Execute and test this code to observe the versatility of Quick Sort with various data types.

Example 2: Sorting an Array of Floating-Point Numbers

#include <iostream>

void swap(double &a, double &b) {
    double temp = a;
    a = b;
    b = temp;
}

int partition(double arr[], int low, int high) {
    double pivot = arr[high];
    int i = low - 1;

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

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

void quickSort(double 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() {
    double arr[] = {9.1, 7.2, 5.3, 11.4, 2.5, 1.6};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original Array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    quickSort(arr, 0, n - 1);

    std::cout << "Sorted Array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

Original Array: 9.1 7.2 5.3 11.4 2.5 1.6
Sorted Array: 1.6 2.5 5.3 7.2 9.1 11.4

Explanation:

• ✅ Choose a pivot element from the array.
• ✅ Rearrange the elements so that elements less than or equal to the pivot are on one side, and elements greater than the pivot are on the other side.
• ✅ Recursively apply Quick Sort to the sub-arrays on both sides of the pivot.
• ✅ The recursion stops when sub-arrays have zero or one element.
• ✅ The original array is sorted as elements are correctly positioned relative to the pivot.
• ✅ The process is repeated for each sub-array created during partitioning.
• ✅ Quick Sort is an efficient, comparison-based sorting algorithm.
• ✅ Average-case time complexity is O(n log n), making it one of the fastest general-purpose sorting algorithms.
• ✅ Pivot selection can impact performance.
• ✅ Quick Sort sorts in-place, requiring no additional memory.
• ✅ Worst-case time complexity is O(n^2) if pivot selection is consistently poor.
• ✅ Frequently used for sorting large datasets.

Example 3: Sorting a Custom Object

#include <iostream>
#include <vector>
#include <algorithm>

class Student {
public:
    std::string name;
    int score;

    Student(std::string n, int s) : name(n), score(s) {}
};

bool compareStudents(const Student &a, const Student &b) {
    return a.score < b.score;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 72},
        {"Charlie", 94},
        {"David", 68},
        {"Eve", 91}
    };

    std::cout << "Original Students:" << std::endl;
    for (const Student &student : students) {
        std::cout << student.name << " - " << student.score << std::endl;
    }

    std::sort(students.begin(), students.end(), compareStudents);

    std::cout << "Sorted Students (by score):" << std::endl;
    for (const Student &student : students) {
        std::cout << student.name << " - " << student.score << std::endl;
    }

    return 0;
}

Output:

Original Students:
Alice - 85
Bob - 72
Charlie - 94
David - 68
Eve - 91

Sorted Students (by score):
David - 68
Bob - 72
Alice - 85
Eve - 91
Charlie - 94

Explanation:

• ✅ Student Class:

A personalized class called Student is created to symbolize individuals enrolled in educational institutions.

Each instance of the Student class contains two properties: name (a string) and grade (an integer value).

A constructor is given to set up these attributes during the creation of a Student instance.

• ✅ Function for Comparing:

A personalized function for comparing students called compareStudents has been established.

This function accepts a pair of Student instances as parameters and evaluates them according to their score properties.

It evaluates as true when the initial student's score is lower than the second student's score, suggesting the first student's priority in the sorted sequence.

• ✅ Primary Function:

Within the primary function, an array named pupils is instantiated.

This array holds multiple instances of Student objects, each representing an individual student with a name and a corresponding score.

• ✅ Displaying Initial Students:

The application displays the initial roster of students on the screen.

When iterating through every student in the students vector, the program showcases the name and score of each student.

• ✅ Arranging Students:

The std::sort function is employed to organize the elements in the students vector.

It reorganizes the students according to their scores in increasing order.

The compareStudents function serves as the basis for comparing students to establish their order when sorting.

• ✅ Displaying Sorted Students:

After arranging the data, the software displays the roster of students once more on the screen.

This time, it presents the students in increasing order based on their scores, displaying both their names and scores.

In essence, this tutorial illustrates the process of declaring a bespoke class (Student), generating instances of said class, arranging them according to a designated characteristic (score), and showcasing the initial and organized collections of students. The arrangement is executed utilizing the std::sort function alongside a personalized comparative function.

In this instance, a bespoke Student class is employed, and Quick Sort is utilized to arrange a vector of Student instances according to their scores.

These instances showcase the versatility of Quick Sort in organizing diverse data types and personalized objects. Adapting Quick Sort to suit a range of data structures involves creating suitable comparison functions or operator overloads tailored to your particular requirements.

Applications of Quick Sort:

QuickSort is a popular sorting algorithm that works by partitioning an array into two sub-arrays and recursively sorting them. It is known for its efficiency and is widely used in various applications where sorting is required. Here are some common applications of QuickSort:

• ✅ General Sorting: QuickSort is primarily used for sorting arrays or lists of elements. It is efficient and has an average-case time complexity of O(n log n). Therefore, it is commonly used in programming languages and libraries for sorting collections of data.
• ✅ Numerical Analysis: QuickSort can be applied in numerical analysis to solve problems such as finding the median, quartiles, or other statistical calculations. It allows for efficient sorting of large datasets in these scenarios.
• ✅ Database Systems: QuickSort can be utilized in database systems for sorting large amounts of data efficiently. Sorting is a fundamental operation in database management systems when retrieving or displaying sorted results.
• ✅ Implementing Other Algorithms: QuickSort is often used as a subroutine within other algorithms. For example, it can be used as a part of divide-and-conquer algorithms like MergeSort or in graph algorithms like Kruskal's algorithm for minimum spanning trees.
• ✅ Order Statistics: QuickSort can be employed to find the kth smallest (or largest) element in an array. By selecting a pivot element and partitioning the array, it is possible to quickly determine the kth element without sorting the entire array.
• ✅ File Systems: QuickSort is applicable in file systems to sort and organize files and directories based on names, sizes, or other attributes. It helps in improving search and retrieval operations within file systems.
• ✅ Computational Biology: QuickSort is used in various bioinformatics applications, such as DNA sequence alignment, genome assembly, or identifying similar sequences. Sorting plays a vital role in these processes, and QuickSort offers efficient solutions.
• ✅ Pivot Selection: The concept of selecting a pivot element in QuickSort has applications in various fields, such as data mining, clustering, and machine learning algorithms. Choosing an appropriate pivot can significantly impact the performance of these algorithms.
• ✅ Language Processing and Natural Language Processing (NLP): QuickSort can be utilized in language processing and NLP tasks that involve sorting words, phrases, or sentences. It is often used in applications such as text analysis, information retrieval, and machine translation.

Advantages of Quick Sort:

• ✅ Efficiency: QuickSort is known for its efficient average-case performance. It has an average time complexity of O(n log n), which makes it one of the fastest sorting algorithms available. In practice, QuickSort often outperforms other sorting algorithms, especially for large datasets.
• ✅ In-place Sorting: QuickSort performs sorting in-place, which means it doesn't require additional memory proportional to the size of the input. It rearranges the elements within the original array, reducing the need for extra space and making it memory efficient.
• ✅ Simplicity: The algorithm's concept is relatively simple and easy to understand, consisting of partitioning the array and recursively sorting the sub-arrays. The simplicity of QuickSort makes it easier to implement and debug compared to more complex sorting algorithms.
• ✅ Good Average-case Performance: QuickSort's average-case performance is typically better than many other sorting algorithms, such as MergeSort or HeapSort. It is well-suited for situations where the input data is randomly distributed or when the input size is large.
• ✅ Tail Recursion Optimization: QuickSort can be optimized using tail recursion, which reduces the amount of stack space required during recursive calls. This optimization helps prevent stack overflow errors and makes QuickSort more efficient for large datasets.
• ✅ Cache Efficiency: QuickSort has good cache efficiency due to its sequential memory access pattern. It tends to exhibit good performance on modern computer architectures that utilize caching, as accessing nearby memory locations can be faster.
• ✅ Inherent Parallelism: QuickSort can be parallelized efficiently, allowing for concurrent execution on multiple processors or threads. The partitioning step lends itself well to parallelization, making QuickSort a suitable choice for parallel computing environments.
• ✅ Randomized Version: QuickSort can be randomized by selecting a random pivot element during partitioning. This helps avoid worst-case scenarios and ensures a more balanced partitioning, improving the average-case performance and reducing the likelihood of degenerate inputs.

The benefits of QuickSort make it a popular option in various scenarios that involve sorting tasks. Nevertheless, it is crucial to highlight that QuickSort may exhibit a worst-case time complexity of O(n^2) under specific conditions, albeit this occurrence is infrequent in real-world applications.