English
Menu

Data Structures and Algorithms

The array 29, 10, 14, 37, 13 is sorted in ascending order with selection sort, which finds the minimum of the unsorted part and swaps it with the first element of the unsorted part. What is the array after this step has been done twice?

  1. A10, 13, 14, 37, 29
  2. B10, 14, 29, 37, 13
  3. C10, 14, 13, 29, 37
Show answer and explanation

Answer: A. 10, 13, 14, 37, 29

The first step swaps the overall minimum 10 with 29 at the front, giving 10, 29, 14, 37, 13. The second step swaps 13, the minimum from the second element on, with 29 in the second position, giving 10, 13, 14, 37, 29. Selection sort always makes n(n−1)/2 comparisons but at most one swap per step, which can be an advantage when writes are expensive. 10, 14, 29, 37, 13 is the array after insertion sort has inserted two elements, and 10, 14, 13, 29, 37 is the array after two passes of bubble sort.

  • A. Correct. 10 and then 13 are swapped to the front.
  • B. This is the array after insertion sort has inserted 10 and 14.
  • C. This is the array after two passes of bubble sort.
Practice this topic Back to topic

Related calculators

Sorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write countsDijkstra's algorithm calculatorCompute shortest paths and distances from a list of weighted edges, and follow each step of finalizing vertices in a table and a diagram

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. An array of 10 elements is sorted in ascending order with insertion sort. Each element from the second one on is taken out and compared with the elements to its left, starting with its left neighbor, until an element less than or equal to it is found or the front is reached. How many comparisons are made when the array is already in ascending order, and when it is in descending order?
  2. Which sorting algorithm is O(n log n) even in the worst case and sorts with almost no extra memory such as a work array?
  3. The (name, score) records (A, 80), (B, 70), (C, 80), (D, 70) are in this order. If they are sorted by score in ascending order with a stable sort, in what order do the names appear?
  4. Which is a typical case in which quicksort takes O(n²) time?
  5. In merge sort, the two sorted runs 1, 4, 7, 9 and 2, 3, 8, 10 are merged into one by repeatedly comparing their front elements and outputting the smaller. When one run is empty, the rest of the other is output without comparisons. How many comparisons are made?