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