Lecture 347:- Let's Code Quick Sort

Here's a C++ implementation of the Quick Sort algorithm:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Function to swap two elements void swap(int& a, int& b) {    int temp = a;    a = b;    b = temp; } // Partition the array and return the pivot index int partition(vector<int>& arr, int low, int high) {    int pivot = arr[high]; // Choose the last element as the pivot    int i = low - 1;       // Index of smaller element    for (int j = low; j <= high - 1; j++) {        if (arr[j] < pivot) {            i++;            swap(arr[i], arr[j]);        }    }    swap(arr[i + 1], arr[high]); // Place the pivot in its correct position    return i + 1;                // Return the pivot index } // Quick Sort function void quickSort(vector<int>& arr, int low, int high) {    if (low < high) {        // Partition the array and get the pivot index        int pivotIndex = partition(arr, low, high);        // Recursively sort the left and right sub-arrays        quickSort(arr, low, pivotIndex - 1);        quickSort(arr, pivotIndex + 1, high);    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};    cout << "Original Array: ";    display(arr);    quickSort(arr, 0, arr.size() - 1);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this program, the quickSort function takes a vector of integers as input and sorts it using the Quick Sort algorithm. The partition function is used to rearrange the elements and return the pivot index. The display function is used to print the elements of the array before and after sorting.

When you run this code, it will display the original array and then the sorted array after applying the Quick Sort algorithm.