## DEV Community is a community of 697,485 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Quick sort algorithm

Aya Bouchiha
Full stack web developer
Updated on ・2 min read

## Definition of quicksort

Quicksort is a type of Divide and Conquer algorithm like merge sort, it works by choosing an element as a pivot from the giving array, and appending the greater elements to the selected pivot, and shifting the smaller elements before it.

## Time and Space complexity

The space complexity of quicksort is O(log n)

best-case average case worst-case
O(n log n) O(n log n) O(n^2) when the list is already sorted, or the pivot is min or max value of the giving list

## Implementation of quick sort using python

def QuickSortAlgorithm(arr: list) -> list:
"""
[ name ] => Quick Sort
[ type ] => Sorting algorithms
[ time complexity ] => (
1. best case:  O(n log n)
2. average case: O(n log n)
3. worst case: O(n^2) { when the pivot is the (min or max) value of the giving list, or the list is already sorted }
)
[ space complexity ] => O(log n)
[params] => (
arr {list} list to sort
)
[return] => {list} sorted list
"""
# size of array
n = len(arr)
if n <= 1:
return arr
# pivote = arr[mid]
pivot = arr[n // 2]
smallerThanPivot = []
greaterThanPivot = []
for i in range(len(arr)):
# do not append pivot to (greaterThanPivot) => continue
if arr[i] == pivot:
continue
# if the element is greater than or equal pivot
if arr[i] >= pivot:
# append the element that is greater than pivot to greaterThanPivot array
greaterThanPivot.append(arr[i])
else:
# if the element is smaller than pivot append it to smallerThanPivot
smallerThanPivot.append(arr[i])

return QuickSortAlgorithm(smallerThanPivot) + [pivot] + QuickSortAlgorithm(greaterThanPivot)

#day_12