Back to list

Quick Sort

A highly efficient, divide-and-conquer algorithm. It picks an element as a 'pivot' and partitions the array.

Ready to divide and conquer...Items: 8
37
31
51
13
12
62
86
18
Speed
Comp
0
Swaps
0
Array Controls

Time Complexity

Best
O(n log n)
Avg
O(n log n)
Worst
O(n²)

Space Complexity

Auxiliary SpaceO(log n)

Algorithm Details

Quick Sort works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This process is repeated until the entire array is sorted.

How it works

  1. Pivot Selection: Choose an element from the array to be the pivot.
  2. Partitioning: Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position.
  3. Recursion: Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Complexity

  • Time Complexity: O(n log n) on average, O(n²) in worst case (rare).
  • Space Complexity: O(log n) (stack space).

Implementation

1def quick_sort(arr):
2  if len(arr) <= 1:
3      return arr
4  else:
5      pivot = arr[0]
6      less = [x for x in arr[1:] if x <= pivot]
7      greater = [x for x in arr[1:] if x > pivot]
8      return quick_sort(less) + [pivot] + quick_sort(greater)
9
10# Example usage
11arr = [10, 7, 8, 9, 1, 5]
12sorted_arr = quick_sort(arr)
13print("Sorted array:", sorted_arr)