Sorting algorithms：練習問題

A bubble sort algorithm is being used to sort the list [7, 4, 9, 2]. How many comparisons will be performed in total during the first pass of the algorithm?

A bubble sort algorithm is used to sort a list of 6 elements. In the worst-case scenario, where the list is in descending order and must be sorted into ascending order, how many total comparisons are made if no early-exit optimization is used?

Which of the following statements correctly distinguishes merge sort from bubble sort regarding space complexity?

Which of the following describes the fundamental approach used by the merge sort algorithm?

During the merge sort of a list with 8 elements, what is the maximum number of times the list is split (the depth of the recursion tree)?

Identify the time complexity of the bubble sort algorithm in its worst-case scenario and explain why it is considered particularly inefficient for large datasets.

Explain the Divide and Conquer strategy used by the merge sort algorithm during its execution.

A dataset consists of a very large list of names. If memory efficiency is a higher priority than raw processing speed, explain why bubble sort might still be rejected in favour of merge sort despite the latter's higher space complexity.

An array of integers is currently in the following order: [25, 14, 3, 10, 5]. A bubble sort algorithm is applied to sort the array into ascending order.

(a) State the state of the array after the first complete pass.
(b) Explain why bubble sort has a worst-case time complexity of \(O(n^2)\).

A programmer is choosing between Bubble Sort and Merge Sort for a dataset of size \(n\).

(a) State the worst-case time complexity for both algorithms using Big-O notation.
(b) Explain the 'Divide and Conquer' strategy used specifically by the Merge Sort algorithm.
(c) Under what specific condition would Merge Sort be significantly disadvantaged compared to Bubble Sort regarding space complexity?