09 Sorting Algorithms Online Quiz Questions

What property does a stable sorting algorithm guarantee?

True or false: Standard selection sort performs $\Theta(n^2)$ comparisons in its best, average, and worst cases.

Using selection sort that executes one swap operation at the end of each of the first $n-1$ passes, how many swap operations are executed for an array of five elements?

A small array is already nearly sorted, and the goal is to use a simple algorithm that can take advantage of that order. Which algorithm is the most appropriate choice?

Select all algorithms that are described as stable in their standard forms in the material.

True or false: Quicksort can take $O(n^2)$ time when pivot choices repeatedly produce highly unbalanced partitions.

For heap sort in ascending order, which type of heap is built?

Merge sort produces the sorted halves $[3,7,8]$ and $[2,4,9]$. What is the result of merging these halves?

Select all algorithms in this list that can preserve the relative order of equal-key records under the standard conditions described in the material.

True or false: For arbitrary inputs, no comparison-based sorting algorithm can guarantee a worst-case running time in $o(n\log n)$.

Explain what stability means in sorting and why it is useful when records are sorted by multiple fields. Use the equal-score example involving Ana and Cara to support your explanation.

A system requires a sorting algorithm with guaranteed worst-case $O(n\log n)$ time and $O(1)$ extra space. Which algorithm best matches these requirements?

Which sequence is a correct ascending sort of the input [4, 1, 3, 2]?

Bubble sort compares adjacent elements and swaps them when they are out of order. What is the array after the first complete left-to-right pass on [5, 1, 4, 2]?

In a zero-based array representation of a binary heap, what is the parent index of the node at index $5$?

Which sorting algorithm is generally a good choice for a small collection that is already nearly sorted?

A collection is first sorted by last name and then stably sorted by department. Which property ensures that records in the same department remain in their previous last-name order?

Merge sort satisfies the recurrence $T(n)=2T(\frac{n}{2})+\Theta(n)$. What is its asymptotic running time?