Back

Quicksort Visualization

Interactive Quicksort

Visualize the Quicksort algorithm, known for its average-case efficiency.

300ms

Enter an array, select a pivot strategy, and click 'Start Sort'.

How Quicksort Works

Quicksort is another efficient, comparison-based sorting algorithm that uses the Divide and Conquer strategy, but differently from Merge Sort:

  1. Choose Pivot: Select an element from the array as the pivot. Common strategies include picking the first, last, median, or a random element.
  2. Partition: Rearrange the array elements such that all elements smaller than the pivot come before it, and all elements greater than the pivot come after it. After partitioning, the pivot is in its final sorted position. The exact partitioning scheme (e.g., Lomuto, Hoare) affects the implementation details.
  3. Conquer (Recurse): Recursively apply Quicksort to the two subarrays: the one with elements smaller than the pivot, and the one with elements larger than the pivot.

Example Implementation (Conceptual - Lomuto Partition)

function quickSort(arr, low, high) {
    if (low < high) {
        // pi is the partitioning index, arr[pi] is now at the right place
        let pi = partition(arr, low, high);

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

// Lomuto partition scheme
function partition(arr, low, high) {
    // Choosing the last element as the pivot
    let pivot = arr[high];
    
    // Index of smaller element
    let i = low - 1;

    for (let j = low; j < high; j++) {
        // If current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++;
            // Swap arr[i] and arr[j]
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }

    // Swap arr[i+1] and arr[high] (put pivot in correct place)
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1; // Return the partition index
}

// Initial call:
// quickSort(myArray, 0, myArray.length - 1);