Algorithm Speed (2.00) :

Array Size (100) :

Quick Sort :

Author(s) : Tony Hoare Date : 1959

Quicksort is a divide-and-conquer sorting algorithm known for its efficiency. It operates by selecting a pivot element from the data structure (typically an array) and partitioning the remaining elements into two sub-arrays. Elements smaller than the pivot are placed in a sub-array to its left, and elements larger than the pivot are placed in a sub-array to its right. This partitioning is achieved by iterating through the array while maintaining two indices: one for the left sub-array and another for the right. The pivot itself can be chosen in various ways, but common strategies include selecting the first, last, or a median element. Once the partitioning is complete, quicksort recursively sorts the two sub-arrays independently. This process continues until all sub-arrays have a single element (considered sorted) or become empty. The average-case time complexity of quicksort is O(n log n), making it significantly faster than bubble sort or insertion sort for large datasets. However, its worst-case complexity can deteriorate to O(n²), which occurs when the chosen pivot consistently leads to unbalanced partitions.

Time Complexity	O(n log n)
Best Case	O(n log n)
Worst Case	O(n²)
Space Complexity	O(log n)
Stable	No

def quicksort(arr, lo, hi):
	if lo < hi:
		p = partition(arr, lo, hi)  # Partition the array and get the pivot element index.
		quicksort(arr, lo, p-1)  # Recursively sort the left partition.
		quicksort(arr, p+1, hi)  # Recursively sort the right partition.

	def partition(arr, lo, hi):
		pivot = arr[hi]  # Choose the last element as the pivot.
		i = lo - 1  # index of smaller element
		for j in range(lo, hi):
			if arr[j] <= pivot:
				i += 1
				arr[i], arr[j] = arr[j], arr[i]  # swap
		arr[i + 1], arr[hi] = arr[hi], arr[i + 1]  # swap pivot into its final position
		return i + 1

# Test array
arr = [12, 11, 13, 5, 6, 7]
quicksort(arr, 0, len(arr) - 1)
print('Sorted array is:', arr)

function quicksort(arr, lo, hi) {
	if (lo < hi) {
		let p = partition(arr, lo, hi); // Partition the array and get the pivot element index.
		quicksort(arr, lo, p - 1); // Recursively sort the left partition.
		quicksort(arr, p + 1, hi); // Recursively sort the right partition.
	}

	function partition(arr, lo, hi) {
		let pivot = arr[hi]; // Choose the last element as the pivot.
		let i = lo - 1; // index of smaller element
		for (let j = lo; j < hi; j++) {
			if (arr[j] <= pivot) {
				i++;
				[arr[i], arr[j]] = [arr[j], arr[i]]; // swap using destructuring
			}
		}
		[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]; // swap pivot into its final position
		return i + 1;
	}
}

// Test array
let arr = [12, 11, 13, 5, 6, 7];
quicksort(arr, 0, arr.length - 1);
console.log('Sorted array is:', arr);

public static void quicksort(int[] arr, int lo, int hi) {
	if (lo < hi) {
		int p = partition(arr, lo, hi); // Partition the array and get the pivot element index.
		quicksort(arr, lo, p - 1); // Recursively sort the left partition.
		quicksort(arr, p + 1, hi); // Recursively sort the right partition.
	}

	private static int partition(int[] arr, int lo, int hi) {
		int pivot = arr[hi]; // Choose the last element as the pivot.
		int i = lo - 1; // index of smaller element
		for (int j = lo; j < hi; j++) {
			if (arr[j] <= pivot) {
				i++;
				swap(arr, i, j); // swap function call
			}
		}
		swap(arr, i + 1, hi); // swap pivot into its final position
		return i + 1;
	}

	// Swap function for clarity (optional)
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// Test array
	int[] arr = {12, 11, 13, 5, 6, 7};
	quicksort(arr, 0, arr.length - 1);
	System.out.println("Sorted array is:" + java.util.Arrays.toString(arr));
}

func quicksort(arr []int, lo, hi int) {
	if lo < hi {
		p := partition(arr, lo, hi) // Partition the array and get the pivot element index.
		quicksort(arr, lo, p-1) // Recursively sort the left partition.
		quicksort(arr, p+1, hi) // Recursively sort the right partition.
	}

	func partition(arr []int, lo, hi int) int {
		pivot := arr[hi] // Choose the last element as the pivot.
		i := lo - 1 // index of smaller element
		for j := lo; j < hi; j++ {
			if arr[j] <= pivot {
				i++
				arr[i], arr[j] = arr[j], arr[i] // swap using assignment
			}
		}
		arr[i+1], arr[hi] = arr[hi], arr[i+1] // swap pivot into its final position
		return i + 1
	}

	// Test array
	arr := []int{12, 11, 13, 5, 6, 7}
	quicksort(arr, 0, len(arr)-1)
	fmt.Println("Sorted array is:", arr)
}

void quicksort(int arr[], int lo, int hi) {
	if (lo < hi) {
		int p = partition(arr, lo, hi); // Partition the array and get the pivot element index.
		quicksort(arr, lo, p - 1); // Recursively sort the left partition.
		quicksort(arr, p + 1, hi); // Recursively sort the right partition.
	}

	int partition(int arr[], int lo, int hi) {
		int pivot = arr[hi]; // Choose the last element as the pivot.
		int i = lo - 1; // index of smaller element
		for (int j = lo; j < hi; j++) {
			if (arr[j] <= pivot) {
				i++;
				swap(&arr[i], &arr[j]); // swap using pointers
			}
		}
		swap(&arr[i + 1], &arr[hi]); // swap pivot into its final position
		return i + 1;
	}

	// Swap function for clarity (optional)
	void swap(int *a, int *b) {
		int temp = *a;
		*a = *b;
		*b = temp;
	}

	// Test array
	int arr[] = {12, 11, 13, 5, 6, 7};
	const int n = sizeof(arr) / sizeof(arr[0]);
	quicksort(arr, 0, n - 1);
	printf("Sorted array is: ");
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}