Quiz: Mastering Sorting Algorithms — 9 Fragen

1. What is comparison-based sorting?

A. Algorithms that sort data by counting the frequency of each element.

B. Sorting methods that do not compare elements but use other properties like keys or digits.

C. Sorting algorithms that determine order solely through element comparisons.

D. Sorting based on the position of elements in a predefined sequence.

Answer: (C)

Erklärung

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.

2. Which comparison-based sorting algorithm is characterized by repeatedly swapping adjacent elements to order a list?

A. Merge Sort

B. Bubble Sort

C. Heap Sort

D. Quick Sort

Answer: (B)

Erklärung

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.

3. Which of the following is a non-comparison sorting algorithm explicitly mentioned in the course content?

A. Counting Sort

B. Merge Sort

C. Quick Sort

D. Bubble Sort

Answer: (A)

Erklärung

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.

4. What is the typical lower bound time complexity for comparison-based sorting algorithms, as described in the revision sheet?

A. O(n^2)

B. O(n log n)

C. O(log n)

D. O(n)

Answer: (B)

Erklärung

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.

5. What is the primary role of Bubble Sort in data processing?

A. To count the occurrences of each element for sorting

B. To divide data into smaller parts for recursive sorting

C. To compare and swap adjacent elements to sort a list

D. To efficiently sort large datasets using divide-and-conquer

Answer: (C)

Erklärung

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.

6. Which property must a stable sort possess to maintain the original order of equal elements?

A. In-place execution

B. Comparison-based operation

C. Stability

D. Divide and Conquer approach

Answer: (C)

Erklärung

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.

7. Which statement correctly distinguishes non-comparison sorting algorithms from comparison-based sorts?

A. They sort data by comparing elements directly.

B. They do not rely on element comparisons but use properties like keys or digits.

C. They are always faster than comparison sorts for large datasets.

D. They are only used for sorting numeric data.

Answer: (B)

Erklärung

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.

8. Why are divide-and-conquer algorithms like Merge Sort and Quick Sort preferred for large datasets?

A. Because they are comparison-based and have better average-case performance

B. Because they always run in linear time

C. Because they do not require recursion

D. Because they are non-comparison sorts

Answer: (A)

Erklärung

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.

9. What is one key aspect that makes Merge Sort different from algorithms like Bubble Sort or Selection Sort?

A. Merge Sort is based on comparison and divide-and-conquer principles.

B. Merge Sort is non-comparison and relies on counting.

C. Merge Sort is an in-place algorithm that doesn't require additional space.

D. Merge Sort is always faster than Quick Sort.

Answer: (A)

Erklärung

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.