QCM : Mastering Sorting Algorithms — 9 questions

Explication

Comparison-based sorting algorithms determine the order of elements by comparing pairs of items using relational operators like '<' or '>'. This approach is fundamental to algorithms such as Bubble Sort, Selection Sort, and Quick Sort, and is characterized by their reliance on comparisons to decide element order.

Explication

Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order, gradually 'bubbling' larger elements to the end. The other options use different mechanisms: Merge Sort divides and conquers, Heap Sort uses a heap structure, and Quick Sort partitions around pivots.

Explication

Counting Sort is explicitly mentioned as a non-comparison sorting algorithm in the course content. It sorts data by counting the occurrences of each value, rather than comparing elements directly, and operates in linear time under certain conditions.

Explication

The theoretical lower bound for comparison-based sorting algorithms is O(n log n), meaning no comparison sort can do better than this in the general case. The other options are either too slow or too optimistic for the comparison-based model.

Explication

Bubble Sort's main function is to compare adjacent elements and swap them if they are in the wrong order, repeatedly passing through the list until it is sorted. Its purpose is to organize data into sorted order through these comparisons and swaps, making option 0 the correct choice.

Explication

Stability in sorting algorithms ensures that elements with equal keys keep their original order after sorting, which is important in multi-key sorting. The other options relate to different algorithm properties but do not guarantee order preservation.

Explication

Non-comparison sorts like Counting Sort and Radix Sort do not rely on pairwise comparisons but instead utilize properties such as keys or digits, enabling linear time sorting in specific cases. Comparison sorts, in contrast, rely solely on comparisons.

Explication

Merge Sort and Quick Sort are divide-and-conquer algorithms that generally offer superior average-case performance of O(n log n), making them suitable for large datasets. They use recursion to break down the problem, unlike iteratively based sorts.

Explication

Merge Sort is a comparison-based, divide-and-conquer algorithm that divides the data into smaller parts, sorts them, and then merges—this structure differs from Bubble or Selection Sort, which repeatedly swap or select minimum elements without such partitioning.