Module 5

Sorting

The process of putting a collection of elements into ascending (or descending) order.

Selection sort

A sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the minimum value to move from the unsorted part to the end of the sorted part. O(N²) because there are two nested loops.

Insertion Sort

A sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part. O(N²)

Nearly sorted arrays

Contains only a few elements not in sorted order. Insertion sort runtime differs for a nearly sorted input. O(N) b/c O((N-C)*1sorted elements+C*Nunsorted elements)