ALGORITHMS-LAB-V-SEM

EX 02: Implement recursive quick sort algorithm

Algorithm

1. Select a pivot element from the array.
2. Partition the array such that elements less than the pivot are on the left and greater on the right.
3. Recursively apply the same process to the left and right sub-arrays.
4. Repeat until the array is fully sorted.

Code

#include <iostream>
using namespace std;

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

int partition(int arr[], int low, int high) {
    int 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(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);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Unsorted array: ";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Output

Unsorted array: 10 7 8 9 1 5 
Sorted array: 1 5 7 8 9 10

Explanation

• The partition function rearranges elements around the pivot, placing smaller elements to its left and larger elements to its right.
• quickSort recursively calls itself on the left and right sub-arrays until the entire array is sorted.