Quicksort Algorithm | Efficient Divide and Conquer Sorting Method

Description

QuickSort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

How It Works

Choose a pivot element from the array
Partition the array around the pivot
Recursively apply the above steps to the sub-arrays

Visualization

Speed:

Click Start to begin visualization

Implementation


def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

# Helper function to call quicksort
def sort(arr):
    quicksort(arr, 0, len(arr) - 1)
    return arr

# Example usage
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", arr)
    sort(arr)
    print("Sorted array:", arr)


#include <iostream>
#include <vector>

class QuickSort {
private:
    static int partition(std::vector<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++;
                std::swap(arr[i], arr[j]);
            }
        }
        
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }
    
    static void quicksort(std::vector<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);
        }
    }

public:
    static void sort(std::vector<int>& arr) {
        quicksort(arr, 0, arr.size() - 1);
    }
};

// Example usage
int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    std::cout << "Original array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    QuickSort::sort(arr);
    
    std::cout << "Sorted array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    return 0;
}


public class QuickSort
{
    private 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++;
                (arr[i], arr[j]) = (arr[j], arr[i]);
            }
        }
        
        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        return i + 1;
    }
    
    private static void QuickSortRecursive(int[] arr, int low, int high)
    {
        if (low < high)
        {
            int pi = Partition(arr, low, high);
            QuickSortRecursive(arr, low, pi - 1);
            QuickSortRecursive(arr, pi + 1, high);
        }
    }
    
    public static void Sort(int[] arr)
    {
        QuickSortRecursive(arr, 0, arr.Length - 1);
    }
    
    // Example usage
    public static void Main(string[] args)
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        
        Console.WriteLine("Original array: " + string.Join(" ", arr));
        Sort(arr);
        Console.WriteLine("Sorted array: " + string.Join(" ", arr));
    }
}

Complexity Analysis

Case	Time Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n²)

Quick Info

Quick Sort

Description

How It Works

Visualization

Implementation

Complexity Analysis

Advantages and Disadvantages

Advantages

Disadvantages