Table of Contents
Quick sort
Quick sort is an efficient, general-purpose, comparison-based sorting algorithm. It works by partitioning the array into two halves around a pivot element, and recursively sorting the two halves.
The quick sort algorithm was invented by Tony Hoare in 1959. It was first published in 1961 in a paper called “Algorithm 64: Quicksort” in the journal Communications of the ACM.
Quick sort is now one of the most widely used sorting algorithms and is included in the standard libraries of many programming languages.
Quick sort Pseudocode Code
function quickSort(array) if length of array <= 1 return array pivot = select pivot element from array left = elements in array less than pivot right = elements in array greater than pivot return concatenate(quickSort(left), pivot, quickSort(right)) function select pivot element(array) return any element in array
The time complexity of quick sort is O(n*log(n)) in the average case and O(n^2) in the worst case. However, the worst-case time complexity can be avoided with proper pivot selection. Quick sort is generally faster in practice than merge sort, but it is not a stable sort, meaning that the order of elements that compare as equal may not be preserved.
Step By Step Explanation
Here is a step-by-step explanation of the quick sort algorithm:
- If the length of the array is 0 or 1, return the array. This is the base case of the recursive algorithm.
- Select a pivot element from the array. This element will be used to partition the array into two halves.
- Create two empty arrays called “left” and “right”.
- Iterate through the array and add each element to the “left” array if it is less than the pivot, and add it to the “right” array if it is greater than the pivot.
- Recursively sort the left array by calling the quick sort function on it.
- Recursively sort the right array by calling the quick sort function on it.
- Concatenate the sorted left array, the pivot element, and the sorted right array, and return the result.
- Repeat the process until the base case is reached and the array is completely sorted.
The pivot element can be chosen in many ways, such as taking the first element of the array, the last element, the median, or a random element. The choice of pivot can greatly affect the performance of the algorithm, with a good pivot selection leading to faster sorting.
Quick Sort in Multiple Languages
C++
#include <iostream> #include <vector> using namespace std; int partition(vector<int>& array, int low, int high) { int pivot = array[high]; int i = low - 1; for (int j = low; j < high; j++) { if (array[j] <= pivot) { i++; swap(array[i], array[j]); } } swap(array[i + 1], array[high]); return i + 1; } void quickSort(vector<int>& array, int low, int high) { if (low < high) { int pivotIndex = partition(array, low, high); quickSort(array, low, pivotIndex - 1); quickSort(array, pivotIndex + 1, high); } } int main() { vector<int> array = {4, 2, 6, 1, 3, 5}; quickSort(array, 0, array.size() - 1); for (int i : array) { cout << i << " "; } cout << endl; return 0; }
Python
def quickSort(array, low, high): if low < high: pivotIndex = partition(array, low, high) quickSort(array, low, pivotIndex - 1) quickSort(array, pivotIndex + 1, high) def partition(array, low, high): pivot = array[high] i = low - 1 for j in range(low, high): if array[j] <= pivot: i += 1 array[i], array[j] = array[j], array[i] array[i + 1], array[high] = array[high], array[i + 1] return i + 1 array = [4, 2, 6, 1, 3, 5] quickSort(array, 0, len(array) - 1) print(array)
Java
import java.util.Arrays; public class QuickSort { public static void quickSort(int[] array, int low, int high) { if (low < high) { int pivotIndex = partition(array, low, high); quickSort(array, low, pivotIndex - 1); quickSort(array, pivotIndex + 1, high); } } public static int partition(int[] array, int low, int high) { int pivot = array[high]; int i = low - 1; for (int j = low; j < high; j++) { if (array[j] <= pivot) { i++; int temp = array[i]; array[i] = array[j]; array[j] = temp; } } int temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp; return i + 1; } public static void main(String[] args) { int[] array = {4, 2, 6, 1, 3, 5}; quickSort(array, 0, array.length - 1); System.out.println(Arrays.toString(array)); } }
JavaScript
function quickSort(array, low, high) { if (low < high) { let pivotIndex = partition(array, low, high); quickSort(array, low, pivotIndex - 1); quickSort(array, pivotIndex + 1, high); } } function partition(array, low, high) { let pivot = array[high]; let i = low - 1; for (let j = low; j < high; j++) { if (array[j] <= pivot) { i++; [array[i], array[j]] = [array[j], array[i]]; } } [array[i + 1], array[high]] = [array[high], array[i + 1]]; return i + 1; } let array = [4, 2, 6, 1, 3, 5]; quickSort(array, 0, array.length - 1); console.log(array);
PHP
<?php function quickSort(&$array, $low, $high) { if ($low < $high) { $pivotIndex = partition($array, $low, $high); quickSort($array, $low, $pivotIndex - 1); quickSort($array, $pivotIndex + 1, $high); } } function partition(&$array, $low, $high) { $pivot = $array[$high]; $i = $low - 1; for ($j = $low; $j < $high; $j++) { if ($array[$j] <= $pivot) { $i++; list($array[$i], $array[$j]) = [$array[$j], $array[$i]]; } } list($array[$i + 1], $array[$high]) = [$array[$high], $array[$i + 1]]; return $i + 1; } $array = [4, 2, 6, 1, 3, 5]; quickSort($array, 0, count($array) - 1); print_r($array);
This Post Has One Comment