9 Sorting Algorithms Free Online FlashCards

What is sorting?

Sorting rearranges items into a specified order, such as ascending numerical order or alphabetical order.

What lower bound applies to comparison sorting?

Comparison-based algorithms cannot guarantee a worst-case running time better than $\Omega(n \log n)$ for $n$ arbitrary items.

What does sorting stability mean?

A stable sort preserves the original relative order of records with equal keys.

How does bubble sort move elements?

Bubble sort repeatedly compares adjacent elements and swaps them when they are out of order.

When is bubble sort linear?

With an early-exit test, bubble sort has a best-case time of $O(n)$ when a pass makes no swaps.

What is selection sort’s central operation?

Selection sort repeatedly finds the smallest item in the unsorted portion and swaps it into the first unsorted position.

Why choose selection sort?

Selection sort is useful when minimizing swaps matters, because it performs only about $n$ swaps despite making $O(n^2)$ comparisons.

How does insertion sort build order?

Insertion sort builds a sorted prefix by shifting larger elements right and inserting the next value into the gap.

What is an inversion?

An inversion is a pair of elements that appears in the opposite order from the desired ordering.

When is insertion sort a strong choice?

Insertion sort is often effective for small or nearly sorted arrays because its best-case time is $O(n)$.

What are merge sort’s three stages?

Merge sort divides the array, recursively sorts both halves, and merges the two sorted halves.

What is merge sort’s time complexity?

Merge sort runs in $O(n \log n)$ time in the best, average, and worst cases.