Sorting

From Algorithmist
Jump to navigation Jump to search
Sorting
Algorithms
Bubble sort
Insertion sort
Selection sort
Quicksort
Merge sort
Heap sort
Introsort
Counting sort
Problems
Problems solvable using sorting

Sorting is a fundamental algorithm in Computer Science. A sorting algorithm takes a list as the input, and returns a list in an order. It is often the first step in many algorithms, and thus setting the lower bound for complexity.

Definition[edit]

Given a list S with N elements, is defined as follows:

  • for , .
  • S' is a permutation of S.

Sorting Algorithms and Complexities[edit]

  • n is the number of elements
  • k is the number of distinct objects
Algorithm Time Complexity Space Complexity
Bubble sort - in place, extra space.
Insertion sort - in place, extra space.
Selection sort - in place, extra space.
Merge sort - extra space.
Heap sort - in place, extra space.
Quicksort - expected, and with high probability. inplace.
Introsort - extra space.
Counting sort
Timsort Best case Worst Case