09 Sorting Algorithms Free Online FlashCards

What makes a sorting result correct?

A correct sort produces an ordered sequence containing exactly the input elements; it changes their arrangement, not the data.

What does stability mean in sorting?

Stability preserves the original relative order of records with equal keys.

How does selection sort arrange elements?

Selection sort repeatedly finds the smallest element in the unsorted region and swaps it into the next output position.

How does insertion sort build a sorted array?

Insertion sort builds a sorted prefix one element at a time, shifting larger elements right to insert the next element.

What operation drives bubble sort?

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

What is merge sort’s divide-and-conquer strategy?

Merge sort divides the input into halves, recursively sorts each half, and merges the sorted halves.

What is the central operation in quicksort?

Quicksort partitions around a pivot, recursively sorts the smaller and larger partitions, and combines them around the pivot.

Why can quicksort degrade to quadratic time?

Quicksort has average-case $O(n \log n)$ time with suitable pivots, but poor repeatedly unbalanced partitions cause $O(n^2)$ worst-case time.

How does heap sort produce ascending order?

Heap sort builds a max-heap, repeatedly moves the maximum root to the end, and restores the heap property.

What is the worst-case lower bound for comparison-based sorting?

A comparison-based sort has a worst-case lower bound of $\Omega(n \log n)$ for arbitrary input. Counting sort and radix sort can avoid this bound by using assumptions about the keys.

What does in-place mean for a sorting algorithm?

An in-place algorithm uses only a small amount of extra memory while rearranging the input collection. The standard implementations of selection, insertion, bubble, and heap sort are in-place.

What does extra space measure in sorting?

Extra space is the memory required beyond the input collection. For example, an array implementation of merge sort usually requires $O(n)$ extra space, while standard heap sort uses $O(1)$.