English
Menu

Data Structures and Algorithms

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?

  1. AB, D, A, C
  2. BD, B, A, C
  3. CB, D, C, A
Show answer and explanation

Answer: A. B, D, A, C

A stable sort keeps elements with the same key (here, the score) in their original relative order. B and D, both with 70, stay in the order B, D, and A and C, both with 80, stay in the order A, C, giving B, D, A, C. Bubble sort, insertion sort and merge sort are stable, while selection sort, quicksort and heapsort are generally not. With a stable sort you can sort by several keys, for example sorting by name first and then by score.

  • A. Correct. Records with the same score keep their original order (B before D, A before C).
  • B. B and D, both with 70, are in the reverse of their original order.
  • C. A and C, both with 80, are in the reverse of their original order.
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. Which is a typical case in which quicksort takes O(n²) time?
  2. 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?
  3. A binary heap is stored in an array a[0], a[1], a[2], … with the root at a[0], filling each level from left to right starting at the top. Which are the children and the parent of a[4]?
  4. A max-heap, in which each parent's value is at least as large as its children's, is stored in an array with the root at a[0]. 45 is added to the heap 50, 30, 40, 10, 20, 35 by placing it at the end and then swapping it with its parent as long as it is larger than the parent. What is the resulting array?
  5. When a binary search tree is traversed in in-order (visiting the left subtree, then the node, then the right subtree), how are the values of the visited nodes ordered? Assume all values are distinct.