Quick Sort Algorithm in C, C++ & Java with Examples

Introduction

QuickSort is one of the fastest and most efficient sorting algorithms, widely used in competitive programming and real-world applications. It follows the Divide and Conquer approach to sort an array efficiently.

This article covers:

• The working principle of QuickSort
• A step-by-step implementation in C, C++, and Java
• The time complexity analysis
• A comparison with Merge Sort to determine which is better

For a better understanding, Merge Sort Algorithm is a recommended prerequisite.

What is QuickSort?

QuickSort works by selecting a pivot element and partitioning the array around it so that:

• Elements smaller than the pivot move to its left
• Elements larger than the pivot move to its right

This process continues recursively until the array is broken down into single-element subarrays, which are then combined to form the final sorted array.

How to Choose a Pivot?

• The first element
• The last element
• The middle element (Ideal for reducing worst-case complexity)

A visual representation of how elements are rearranged during each partitioning step would enhance this explanation.

How QuickSort Works: Step-by-Step Example

Let’s walk through an example to understand how QuickSort sorts an array.

Given array: [10, 80, 30, 90, 40, 50, 70]
Step 1: Choose a pivot (e.g., the last element, 70) and partition the array.
Step 2: Move elements smaller than 70 to the left and larger ones to the right.
Step 3: Recursively apply QuickSort on left and right subarrays.

A step-by-step animation or diagram illustrating the partitioning process would be beneficial here.

QuickSort Implementation in C, C++, and Java

C Implementation of QuickSort

#include <stdio.h>

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++)
        printf("%d ", arr[i]);
    printf("\n");
}

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

C++ Implementation of QuickSort

#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]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Java Implementation of QuickSort

class QuickSort {
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static 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, j);
            }
        }
        swap(arr, i + 1, high);
        return (i + 1);
    }

    static 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);
        }
    }

    static void printArray(int[] arr) {
        for (int num : arr)
            System.out.print(num + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        printArray(arr);
    }
}

Time Complexity Analysis of QuickSort

Key Factors Influencing Complexity:

• Choosing a good pivot (close to the median) ensures O(n log n) complexity.
• If the pivot is always the smallest or largest element, complexity worsens to O(n²).

QuickSort vs MergeSort: Which is Better?

Conclusion:

• QuickSort is preferred for arrays due to in-place sorting.
• MergeSort is better for linked lists and stable sorting needs.

Conclusion

QuickSort is a highly efficient sorting algorithm widely used in real-world applications and competitive programming. By choosing a good pivot and using in-place partitioning, QuickSort ensures optimal performance in most cases.

For more sorting algorithms, check out:

• Selection Sort
• Insertion Sort
• Merge Sort
• Heap Sort

This SEO-optimized article improves search ranking by incorporating keywords like QuickSort, sorting in C, C++, Java, Divide and Conquer, and QuickSort vs MergeSort. Let me know if you need further refinements!