Sorting Algorithms

Source code: src/pydsadoc/sorting/__init__.py

A Sorting Algorithm is used to rearrange a given array or list of elements in an order.

Comparison Based Sort

We compare the elements in a comparison-based sorting algorithm.

Basics Sorting Algorithms

bubble_sort(arr: list[int]) → None

Sort a list of numbers in ascending order.

Stable. Best Case: \(O(n)\). Average Case: \(O(n^2)\). Worst Case: \(O(n^2)\).

insertion_sort(arr: list[int]) → None

Sort a list of numbers in ascending order.

Stable. Best Case: \(O(n)\). Average Case: \(O(n^2)\). Worst Case: \(O(n^2)\).

selection_sort(arr: list[int]) → None

Sort a list of numbers in ascending order.

Not Stable. Best Case: \(O(n^2)\). Average Case: \(O(n^2)\). Worse Case: \(O(n^2)\).

Advanced Sorting Algorithms

shell_sort(arr: list[int]) → None

Sort a list of numbers in ascending order.

Not Stable. Best Case: \(O(n \log n)\). Average Case: \(O(n^{4/3})\). Worst Case: \(O(n^{3/2})\).

Time complexity is between \(O(n^{1.25})\) and \(O(n^{1.5})\), depending on the chosen gap sequence. It is an optimization of Insertion Sort.

See also

The Sedgewick sequence of increments for Shell sort (best on big values).

heap_sort(arr: list[int]) → None

Sort a list of numbers in ascending order.

Not Stable. Best Case: \(O(n \log n)\). Average Case: \(O(n \log n)\). Worst Case: \(O(n \log n)\).

merge_sort(arr: list[int]) → None

Sort a list of numbers in ascending order.

Stable. Best Case: \(O(n \log n)\). Average Case: \(O(n \log n)\). Worst Case: \(O(n \log n)\).

Space complexity is \(O(n)\).

quick_sort(arr: list[int]) → None

Sort a list of numbers in ascending order.

Not Stable. Best Case: \(O(n \log n)\). Average Case: \(O(n \log n)\). Worst Case: \(O(n^2)\).

Space complexity is \(O(\log n)\).

tim_sort(arr: list[T]) → None

Sort a list of numbers in ascending order.

Non-Comparison Based Sort(TBD)

We do not compare the elements in a non-comparison-based sorting algorithm.

bucket_sort(arr: list[int]) → None

Sort a list of numbers in ascending order(TBD).

counting_sort(arr: list[int]) → None

Sort a list of numbers in ascending order(TBD).

radix_sort(arr: list[int]) → None

Sort a list of numbers in ascending order(TBD).