Sort

Sort#

Contents#

The Sorting Problem#

\(\text{Problem} \quad \text{Sort a sequence of numbers into monotonically increasing order}\)

\( \begin{aligned} \text{ Input} && \text{A sequence of}\,\, n \,\,\text{numbers}\,\, & \langle a_1, a_2, \dotsc, a_n \rangle \\ \text{ Output} && \text{A permutation (reordering)}\,\, & \langle a_1', a_2', \dotsc, a_n' \rangle \,\,\text{of the input sequence such that}\,\, a_1' \le a_2' \le \dotsb \le a_n' \\ \end {aligned} \)

The numbers to be sorted are also known as the keys. Although the problem is conceptually about sorting a sequence, the input comes in the form of an array with \(n\) elements.

Problem / Program Description: Sort an array of \(n\) elements

Input: a positive integer \(n\) and an array of \(n\) numbers \(a_1, \dots, a_n\)

Output: the re-ordering of \(a_1, \dots, a_n\) into \(b_1, \dots, b_n\) such that \(b_j \le b_{j + 1}\) for \(j \in {1, \dots, n - 1}\)

Sections#

Resources#

https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/

YouTube#

  • [ y ] 11-18-2016 Computerphile. “Sorting Secret - Computerphile”.

Terms#

  • [ w ] Bogo Sort

  • [ w ] Bubble Sort

  • [ w ] Cocktail Shaker Sort

  • [ w ] Comb Sort

  • [ w ] Comparison Sort

  • [ w ] Dutch National Flag Problem

  • [ w ] External Sorting

  • [ w ] Heap Sort

  • [ w ] Insertion Sort

  • [ w ] Merge Sort

  • [ w ] Quick Sort

  • [ w ] Selection Sort

  • [ w ] Sorting Algorithm

  • [ w ] Tim Sort

Contents