Sort an Array

XXX. Quicksort Algorithm

Sorting

Divide and Conquer

Problem Statement:

Implement the quicksort algorithm to sort an array in-place. Quicksort is a sorting algorithm based on the divide-and-conquer paradigm, where an array is partitioned into two subarrays based on a pivot, and the process is recursively applied to the subarrays.

Algorithm:

1. Choose a pivot element (typically the last element in the array).
2. Partition the array such that elements smaller than the pivot come before it and elements greater come after it.
3. Recursively apply the quicksort algorithm to the subarrays before and after the pivot.

Complexity:

Time Complexity: O(n log n) on average, O(n²) in the worst case.
Space Complexity: O(log n) due to the recursion stack.

Java Implementation:

public void quicksort(int[] nums, int start, int end) {
    if (start >= end) return; // Base case: subarray has 1 or no elements

    int pIndex = partition(nums, start, end); // Partition array and get pivot index
    quicksort(nums, start, pIndex - 1); // Recur for left subarray
    quicksort(nums, pIndex + 1, end);   // Recur for right subarray
}

int partition(int[] nums, int start, int end) {
    int pivot = nums[end]; // Choose pivot as the last element
    int pIndex = start;    // Initialize partition index

    for (int i = start; i < end; i++) // Traverse elements before the pivot
        if (nums[i] <= pivot) {
            swap(i, pIndex, nums); // Swap smaller element with pIndex
            pIndex++;
        }

    swap(pIndex, end, nums); // Place pivot at its correct position
    return pIndex;
}

void swap(int a, int b, int[] nums) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}
                

Python Implementation:

def quicksort(nums, start, end):
    if start >= end:
        return  # Base case: subarray has 1 or no elements

    p_index = partition(nums, start, end)  # Partition array and get pivot index
    quicksort(nums, start, p_index - 1)  # Recur for left subarray
    quicksort(nums, p_index + 1, end)    # Recur for right subarray

def partition(nums, start, end):
    pivot = nums[end]  # Choose pivot as the last element
    p_index = start    # Initialize partition index

    for i in range(start, end):  # Traverse elements before the pivot
        if nums[i] <= pivot:
            nums[i], nums[p_index] = nums[p_index], nums[i]  # Swap smaller element with p_index
            p_index += 1

    nums[p_index], nums[end] = nums[end], nums[p_index]  # Place pivot at its correct position
    return p_index
                

C++ Implementation:

#include 
using namespace std;

void quicksort(vector& nums, int start, int end) {
    if (start >= end) return; // Base case: subarray has 1 or no elements

    int pIndex = partition(nums, start, end); // Partition array and get pivot index
    quicksort(nums, start, pIndex - 1); // Recur for left subarray
    quicksort(nums, pIndex + 1, end);   // Recur for right subarray
}

int partition(vector& nums, int start, int end) {
    int pivot = nums[end]; // Choose pivot as the last element
    int pIndex = start;    // Initialize partition index

    for (int i = start; i < end; i++) // Traverse elements before the pivot
        if (nums[i] <= pivot) {
            swap(nums[i], nums[pIndex]); // Swap smaller element with pIndex
            pIndex++;
        }

    swap(nums[pIndex], nums[end]); // Place pivot at its correct position
    return pIndex;
}