Quick Sort using Recursion

Quick Sort is an efficient sorting algorithm that uses the “divide and conquer” approach. The algorithm selects a “pivot” element from the array, partitions the array into two sub-arrays such that elements less than the pivot go to the left of it and elements greater than the pivot go to the right, and then recursively applies the same strategy to both sub-arrays.

Here’s the step-by-step explanation along with a C program that implements Quick Sort.

Steps of Quick Sort:

1. Choose a Pivot: A pivot element is selected. Commonly, the last element in the array is used.

2. Partitioning: Re-arrange the array such that:

• All elements less than the pivot are moved to the left.
• All elements greater than the pivot are moved to the right.

3. Recursive Sorting: Recursively apply the same steps to the sub-arrays on the left and right of the pivot.

4. Base Case: The recursion stops when the sub-array has 0 or 1 element, as it is already sorted.

 #include <stdio.h>

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

// Function to partition the array
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 the 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 the smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Recursive QuickSort function
void quickSort(int arr[], int low, int high) 
{
    if (low < high) 
{
        // Partition the array
        int pi = partition(arr, low, high);

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

// Function to print the array
void printArray(int arr[], int size) 
{
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() 
{
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Detailed Explanation:

1. swap function:

• Takes two pointers and swaps their values.
• It’s used during partitioning to move elements.

2. partition function:

• Takes the array and divides it into two parts around a pivot.
• The pivot is chosen as the last element (arr[high]).
• It re-arranges the elements so that those smaller than the pivot are to its left, and those larger are to its right.
• Returns the index of the pivot after partitioning.

3. quickSort function:

• This is the main recursive function that sorts the array.
• It checks if the current array or sub-array is non-empty (low < high), and if so, calls the partition function.
• After partitioning, it recursively sorts the left and right sub-arrays.

4. printArray function:

• This function simply prints the elements of the array.

5. main function:

• Initializes an array with unsorted values.
• Calls the quickSort function to sort the array.
• Prints the original and sorted arrays.

Output:

Original array:
10 80 30 90 40 50 70 
Sorted array:
10 30 40 50 70 80 90

Explanation of Output:

• The original array is [10, 80, 30, 90, 40, 50, 70].
• After applying Quick Sort, the sorted array is [10, 30, 40, 50, 70, 80, 90].

Time Complexity:

• Best and Average Case: O(n log n) where n is the number of elements in the array.
• Worst Case: O(n^2) occurs when the pivot divides the array into extremely unbalanced partitions (e.g., when the array is already sorted, and the pivot is always the largest/smallest element).

This implementation of Quick Sort effectively handles the sorting of an array using recursion, providing efficient sorting for average cases.