AntInLoop

Quick Sort Algorithm Code Implementations

Complete Quick Sort Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Quick Sort Algorithm Guide · Launch Interactive Visualizer

C++ Implementation

// Quick Sort Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>

class QuickSort {
public:
    static std::vector<int> quickSort(const std::vector<int>& arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        std::vector<int> sortedArray = arr;
        quickSortInPlace(sortedArray, 0, sortedArray.size() - 1);
        return sortedArray;
    }
    
private:
    static void quickSortInPlace(std::vector<int>& arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSortInPlace(arr, left, pivotIndex - 1);
            quickSortInPlace(arr, pivotIndex + 1, right);
        }
    }
    
    static int partition(std::vector<int>& arr, int left, int right) {
        // Choose pivot (rightmost element)
        int pivot = arr[right];
        int i = left - 1;
        
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        
        std::swap(arr[i + 1], arr[right]);
        return i + 1;
    }
    
public:
    // Alternative implementation with middle pivot
    static std::vector<int> quickSortMiddlePivot(const std::vector<int>& arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        std::vector<int> sortedArray = arr;
        quickSortMiddlePivotInPlace(sortedArray, 0, sortedArray.size() - 1);
        return sortedArray;
    }
    
private:
    static void quickSortMiddlePivotInPlace(std::vector<int>& arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partitionMiddlePivot(arr, left, right);
            quickSortMiddlePivotInPlace(arr, left, pivotIndex - 1);
            quickSortMiddlePivotInPlace(arr, pivotIndex + 1, right);
        }
    }
    
    static int partitionMiddlePivot(std::vector<int>& arr, int left, int right) {
        int mid = left + (right - left) / 2;
        int pivot = arr[mid];
        
        // Move pivot to end
        std::swap(arr[mid], arr[right]);
        
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        
        std::swap(arr[i + 1], arr[right]);
        return i + 1;
    }
};

CPP Implementation

Time: O(n log n) average, O(n²) worst case | Space: O(n)

// Quick Sort Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>

class QuickSort {
public:
    static std::vector<int> quickSort(const std::vector<int>& arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        std::vector<int> sortedArray = arr;
        quickSortInPlace(sortedArray, 0, sortedArray.size() - 1);
        return sortedArray;
    }
    
private:
    static void quickSortInPlace(std::vector<int>& arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSortInPlace(arr, left, pivotIndex - 1);
            quickSortInPlace(arr, pivotIndex + 1, right);
        }
    }
    
    static int partition(std::vector<int>& arr, int left, int right) {
        // Choose pivot (rightmost element)
        int pivot = arr[right];
        int i = left - 1;
        
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        
        std::swap(arr[i + 1], arr[right]);
        return i + 1;
    }
    
public:
    // Alternative implementation with middle pivot
    static std::vector<int> quickSortMiddlePivot(const std::vector<int>& arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        std::vector<int> sortedArray = arr;
        quickSortMiddlePivotInPlace(sortedArray, 0, sortedArray.size() - 1);
        return sortedArray;
    }
    
private:
    static void quickSortMiddlePivotInPlace(std::vector<int>& arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partitionMiddlePivot(arr, left, right);
            quickSortMiddlePivotInPlace(arr, left, pivotIndex - 1);
            quickSortMiddlePivotInPlace(arr, pivotIndex + 1, right);
        }
    }
    
    static int partitionMiddlePivot(std::vector<int>& arr, int left, int right) {
        int mid = left + (right - left) / 2;
        int pivot = arr[mid];
        
        // Move pivot to end
        std::swap(arr[mid], arr[right]);
        
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        
        std::swap(arr[i + 1], arr[right]);
        return i + 1;
    }
};

JAVA Implementation

// Quick Sort Implementation in Java
public class QuickSort {
    public static int[] quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr.clone();
        }
        
        int[] sortedArray = arr.clone();
        quickSortInPlace(sortedArray, 0, sortedArray.length - 1);
        return sortedArray;
    }
    
    private static void quickSortInPlace(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSortInPlace(arr, left, pivotIndex - 1);
            quickSortInPlace(arr, pivotIndex + 1, right);
        }
    }
    
    private static int partition(int[] arr, int left, int right) {
        // Choose pivot (rightmost element)
        int pivot = arr[right];
        int i = left - 1;
        
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, right);
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // Alternative implementation with middle pivot
    public static int[] quickSortMiddlePivot(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr.clone();
        }
        
        int[] sortedArray = arr.clone();
        quickSortMiddlePivotInPlace(sortedArray, 0, sortedArray.length - 1);
        return sortedArray;
    }
    
    private static void quickSortMiddlePivotInPlace(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partitionMiddlePivot(arr, left, right);
            quickSortMiddlePivotInPlace(arr, left, pivotIndex - 1);
            quickSortMiddlePivotInPlace(arr, pivotIndex + 1, right);
        }
    }
    
    private static int partitionMiddlePivot(int[] arr, int left, int right) {
        int mid = left + (right - left) / 2;
        int pivot = arr[mid];
        
        // Move pivot to end
        swap(arr, mid, right);
        
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, right);
        return i + 1;
    }
}

JAVASCRIPT Implementation

Time: O(n log n) average, O(n²) worst case | Space: O(n)


function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const equal = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] > pivot) {
      right.push(arr[i]);
    } else {
      equal.push(arr[i]);
    }
  }

  return [...quickSort(left), ...equal, ...quickSort(right)];
}

// Example usage:
// const myList = [10, 7, 8, 9, 1, 5];
// const sortedList = quickSort(myList);
// console.log(sortedList); // Output: [1, 5, 7, 8, 9, 10]

PYTHON Implementation

# Quick Sort Implementation in Python
def quick_sort(arr):
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr
    
    # Choose pivot (middle element for better performance)
    pivot_index = len(arr) // 2
    pivot = arr[pivot_index]
    
    # Partition array around pivot
    left = [x for i, x in enumerate(arr) if i != pivot_index and x < pivot]
    right = [x for i, x in enumerate(arr) if i != pivot_index and x > pivot]
    equal = [x for i, x in enumerate(arr) if i == pivot_index or x == pivot]
    
    # Recursively sort left and right partitions
    sorted_left = quick_sort(left)
    sorted_right = quick_sort(right)
    
    # Combine sorted partitions
    return sorted_left + equal + sorted_right

# In-place Quick Sort implementation (more memory efficient)
def quick_sort_in_place(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    if left < right:
        pivot_index = partition(arr, left, right)
        quick_sort_in_place(arr, left, pivot_index - 1)
        quick_sort_in_place(arr, pivot_index + 1, right)
    
    return arr

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