Sorting

Many of programs we see today have something to do with sorting, that given an unsorted, randomly distributed array or list, research the best approach to sort in accordance to a specified alphabetical or numerical order.

Terminologies

Key concepts are introduced in this chapter such as Stable Sort.

Total Order

Total Order is a binary relation on a set of elements that satisfies:

• Antisymmetry: if a ⩾ b and b ⩾ a, then a = b

• Transitivity: if a ⩽ b and b ⩽ c, then a ⩽ c

• Totality: either a ⩽ b or b ⩽ a or both

Adaptive Sort

A sorting algorithm is an adaptive sort scheme if it takes advantage of existing order of an original inputs. The presortedness of the input sequence benefits the sorting algorithm to achieve better running time.

Comparison-based Sort

Sorting algorithms that sort a list of elements base only on the comparisons of pairs without knowing other aspects of elements is comparison-based sort.

Note: Comparison-based Sort assumes no preliminary knowledge about input arrays and thus the "general-purpose sorting method"; if not, some non-comparison based sort could be highly useful.

Sorting Lower Bound

Formal Def: every comparison-based sorting has the worst-case running time of Ω(n ⋅ log n).

Proof: given a randomly distributed array of length n, assume the maximal compares required to sort the entire array is k and there is at least n! permutations to sort (each permutation is possible to yield the correct outcome); In each comparison, we obtain either a True or False that the element is displaced in the right location, then:

2k ⩾ n!, by pigeonhole principle, 2k ⩾ (n/2)n/2, k ⩾ (n/2) ⋅ log (n/2)

According to asymptotic analysis, noting that k ⩾ cn ⋅ log (cn), Τ(n) = Ω(n ⋅ log n)

In-place Sort

Sorting scheme that only a constant number of elements or memory spaces are required to store outside the original array is In-place Sort.

In-place Sort only requires Ο(1) extra space to sort the array. It usually sorts on the original array thus an useful approach to minimize the memory usage while sorting.

Stable Sort

Stable sorting algorithm maintains the relative order of elements with same value. Mathematically, given two records ℛ and 𝒬 with same value, ℛ precedes 𝒬 in the original array, then a Stable Sort will produce a sorted array with ℛ comes before 𝒬.

Table of Contents

• Selection Sort - a naive swapping-based sorting algorithm.
• Bubble Sort - an improved swapping-based sorting technique.
• Insertion Sort - mostly used approach in common sorting tasks.
• Shell Sort - a compensating algorithm for worst-case insertion sort.
• Heap Sort - a type of sorting technique based on min-heap or max-heap data structures.
• Merge Sort - a typical DnC strategy in sorting tasks.
• Quick Sort - a performant algorithm combined with both DnC and Randomization
• Non-Comparison Sort - intro to several non-comparison based sorting algorithms

References

• ICS-161 Design and Analysis of Algorithms, UCI - Lecture Notes in Jan 16, 1996
• CSE-373 Data Structure & Algorithms, UW - Lecture Notes, 2017
• CSC-263 Lecture 13, U of Toronto - Lecture notes, 2006