Table of contents

Quick Sort Algorithm

What is Quick Sort?

Quick Sort is a highly efficient and widely used sorting algorithm based on the divide-and-conquer strategy. It works by selecting a "pivot" element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are then recursively sorted. Quick Sort is often faster in practice than other O(n log n) algorithms and has an average-case time complexity of O(n log n).

How Quick Sort Works

Quick Sort works by recursively dividing the array into smaller subarrays and sorting them individually. The key operation in Quick Sort is the partition function, which rearranges the elements in such a way that all elements less than the pivot are on the left of the pivot, and all elements greater than the pivot are on the right.

Step-by-step explanation:

  1. Pick a Pivot: Choose an element from the array to serve as the pivot. Various methods can be used to select the pivot, such as selecting the first element, the last element, a random element, or the median.
  2. Partition the Array: Rearrange the array so that elements smaller than the pivot are on the left, and elements larger than the pivot are on the right.
  3. Recursively Apply Quick Sort: Recursively apply the same process to the subarrays formed by dividing the array around the pivot.

Example of Quick Sort

Let’s take an example of sorting the array [10, 80, 30, 90, 40, 50, 70]:

  1. Initial List: [10, 80, 30, 90, 40, 50, 70]
  2. Pick a Pivot: Let's choose 70 as the pivot (the last element).
  3. Partition:
    • Elements less than 70: [10, 30, 40, 50]
    • Elements greater than 70: [80, 90]
    • After partitioning: [10, 30, 40, 50, 70, 90, 80]
  4. Recursively Apply Quick Sort:
    • Left subarray: [10, 30, 40, 50]
    • Right subarray: [90, 80]
  5. Continue recursively sorting the subarrays until the entire array is sorted.

C++ Program to implement Quick Sort Algorithm

cpp
#include <iostream>
using namespace std;

// Function to partition the array on the basis of pivot
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; j++) {
        // If the current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++;  // Increment the index of the smaller element
            swap(arr[i], arr[j]);  // Swap the elements
        }
    }

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

// Function to perform quicksort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Partition the array and get the partition index
        int pi = partition(arr, low, high);

        // Recursively sort the elements before 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++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Main function
int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    quickSort(arr, 0, n - 1);

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

    return 0;
}

Java Program to implement Quick Sort Algorithm

java
public class Main {
    // Function to partition the array on the basis of pivot
    public static 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; j++) {
            // If the current element is smaller than the pivot
            if (arr[j] < pivot) {
                i++;  // Increment the index of the smaller element
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;  // Swap the elements
            }
        }

        // Swap the pivot element with the element at index i+1
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;  // Return the partitioning index
    }

    // Function to perform quicksort
    public static void quickSort(int arr[], int low, int high) {
        if (low < high) {
            // Partition the array and get the partition index
            int pi = partition(arr, low, high);

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

    // Function to print the array
    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Main function
    public static void main(String args[]) {
        int arr[] = {10, 80, 30, 90, 40, 50, 70};

        System.out.println("Original array:");
        printArray(arr);

        quickSort(arr, 0, arr.length - 1);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Python Program to implement Quick Sort Algorithm

python
# Function to partition the array on the basis of pivot
def partition(arr, low, high):
    pivot = arr[high]  # Choosing the last element as the pivot
    i = low - 1        # Index of the smaller element

    for j in range(low, high):
        # If the current element is smaller than the pivot
        if arr[j] < pivot:
            i += 1  # Increment the index of the smaller element
            arr[i], arr[j] = arr[j], arr[i]  # Swap the elements

    # Swap the pivot element with the element at index i+1
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1  # Return the partitioning index

# Function to perform quicksort
def quick_sort(arr, low, high):
    if low < high:
        # Partition the array and get the partition index
        pi = partition(arr, low, high)

        # Recursively sort the elements before and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# Function to print the array
def print_array(arr):
    print(" ".join(map(str, arr)))

# Main function
if __name__ == "__main__":
    arr = [10, 80, 30, 90, 40, 50, 70]

    print("Original array:")
    print_array(arr)

    quick_sort(arr, 0, len(arr) - 1)

    print("Sorted array:")
    print_array(arr)

Properties of Quick Sort

  • Time Complexity:
    • Best Case: O(n log n) - when the partitioning divides the array into balanced subarrays.
    • Average Case: O(n log n)
    • Worst Case: O(n²) - when the pivot is always the smallest or largest element, causing unbalanced partitions.
  • Space Complexity: O(log n) - for the recursive call stack.
  • Stability: Quick Sort is not a stable sorting algorithm, meaning it may change the relative order of equal elements.
  • Adaptability: Quick Sort is not adaptive. It always performs O(n log n) comparisons on average, regardless of whether the input is already sorted.

When to Use Quick Sort

Quick Sort is generally the fastest sorting algorithm for large datasets. Its average-case time complexity of O(n log n) and in-place sorting (using only O(log n) extra space) make it highly efficient for most practical applications. However, care must be taken in choosing the pivot to avoid the worst-case performance of O(n²).

DSA

Related Articles