FREE! Click here to Join FunTrivia. Thousands of games, quizzes, and lots more!
Quiz about Sorting
Quiz about Sorting

Sorting Trivia Quiz


How do computers sort data?

A multiple-choice quiz by Hegh. Estimated time: 5 mins.
  1. Home
  2. »
  3. Quizzes
  4. »
  5. Science Trivia
  6. »
  7. Computers
  8. »
  9. Software and Programming

Author
Hegh
Time
5 mins
Type
Multiple Choice
Quiz #
271,006
Updated
Dec 03 21
# Qns
10
Difficulty
Tough
Avg Score
6 / 10
Plays
1691
Awards
Top 35% Quiz
Last 3 plays: Guest 107 (10/10), Guest 149 (9/10), Guest 75 (3/10).
- -
Question 1 of 10
1. One of the simplest sorting algorithms is called bubble sort. Do you know why? Hint


Question 2 of 10
2. In which case would an insertion sort perform best, assuming it was reading the array to be sorted from beginning to end (as opposed to randomly)? Hint


Question 3 of 10
3. What is the first change that selection sort would make to this sequence to put it into ascending order: "3 1 4 2"? Hint


Question 4 of 10
4. A mergesort works by first breaking a sequence in half a number of times so it is working with smaller pieces. When does it stop breaking the list into sublists (in its simplest version)? Hint


Question 5 of 10
5. Quicksort works by choosing a pivot value and moving list elements around. Each element less than the pivot will be closer to the beginning of the list than the pivot, and each element greater than the pivot will be closer to the end of the list. By doing this operation many times with different pivots, the list will become sorted. For the fastest operation, which would be the best pivot value? Hint


Question 6 of 10
6. Which algorithm would work best to sort data as it arrives, one piece at a time, perhaps from a network? Hint


Question 7 of 10
7. Which of these sorting algorithms could easily be parallelized? (Given any number of extra computers to help with the task, which would require the least extra programming to have them work together to sort the list)? Hint


Question 8 of 10
8. When would it be a good idea to use bubble sort? Hint


Question 9 of 10
9. A 'stable' sort is a sort that will not change the relative order of any pair of equal values in a list. Which of these is (in its default implementation) *not* a stable sort? Hint


Question 10 of 10
10. Which of the following sorting algorithms cannot be performed in-place (it needs scratch-space apart from the array being sorted)? Hint



(Optional) Create a Free FunTrivia ID to save the points you are about to earn:

arrow Select a User ID:
arrow Choose a Password:
arrow Your Email:




Most Recent Scores
Mar 09 2024 : Guest 107: 10/10
Mar 07 2024 : Guest 149: 9/10
Mar 06 2024 : Guest 75: 3/10
Mar 06 2024 : badro12: 5/10
Feb 28 2024 : Guest 24: 5/10
Feb 26 2024 : Guest 195: 4/10
Feb 21 2024 : Guest 147: 7/10
Feb 21 2024 : Guest 86: 0/10
Feb 20 2024 : Guest 109: 4/10

Score Distribution

quiz
Quiz Answer Key and Fun Facts
1. One of the simplest sorting algorithms is called bubble sort. Do you know why?

Answer: Smaller elements 'bubble' to the top

The idea behind the bubble sort is to pass through the list of elements to be sorted a number of times. In each pass, you examine two adjacent elements at a time. If the one closer to the beginning of the list is larger, you swap the two, allowing the smaller element to 'bubble' towards the top, as if it were lighter. So, sorting the sequence "3 1 4 2" would go like this (the - marks the pair of elements about to be compared):

Start: 3-1 4 2
1: 1 3-4 2
2: 1 3 4-2
3: 1-3 2 4
4: 1 3-2 4
5: 1 2 3-4
6: 1-2 3 4
7: 1 2-3 4
8: 1 2 3-4

The computer doesn't know that the list is sorted before doing the last pass (steps 6-8), so it cannot skip them.

Bubble sort is one of the slower sorting methods, taking approximately n * n steps to sort a list with n elements in it.
2. In which case would an insertion sort perform best, assuming it was reading the array to be sorted from beginning to end (as opposed to randomly)?

Answer: If the array was already sorted

The insertion sort works by moving each element of the array being sorted to a new array, placing it so that the new array always remains sorted. It shifts the elements in the sorted array to make room as it goes. So, sorting the sequence "3 1 4 2" would go something like this:

Start:
Original: 3 1 4 2
Sorted: x x x x

Step 1:
Original: x 1 4 2
Sorted: 3 x x x

Step 2:
Original: x x 4 2
Sorted: 1 3 x x

Step 3:
Original: x x x 2
Sorted: 1 3 4 x

Step 4:
Original: x x x x
Sorted: 1 2 3 4

So a sorted input array would not need to shift anything at each step, as each element would simply be appended to the array. A reverse-sorted input, however, would shift everything by the maximum amount.

In the best case, insertion sort can take about n steps to sort n elements, and in the worst case it will take n * n steps.
3. What is the first change that selection sort would make to this sequence to put it into ascending order: "3 1 4 2"?

Answer: 1 3 4 2

Selection sort works by moving a cursor one element at a time through the array, and searching for the minimum element between the cursor and the end of the array. The element under the cursor is then swapped with the minimum element. Here is how selection sort would sort the sequence "3 1 4 2" (the * indicates the position of the cursor):

Start: *3 1 4 2
1: 1 *3 4 2
2: 1 2 *4 3
3: 1 2 3 *4 (no point looking for another swap, we're at the end)

Selection sort is relatively slow, despite the small number of steps shown here. We skipped the parts where the computer searches for the minimum value for each swap. To sort an array with n elements, selection sort will take about n * n steps.
4. A mergesort works by first breaking a sequence in half a number of times so it is working with smaller pieces. When does it stop breaking the list into sublists (in its simplest version)?

Answer: When each sublist has one element

Mergesort, in its simplest version, will break the list into smaller and smaller sublists until each contains but one element. Why? Because a list containing one element is sorted!

The next step is to merge two of these sublists by comparing the elements in each, one at a time, until one list or the other is empty. Then the rest of the non-empty list is tacked onto the end of the list you were building, and you move onto the next pair of sublists. Here is an example, let's sort the list "3 6 2 4 1 5":

Start: 3 4 2 5 1 5

Split 1:
3 4 2 / 6 1 5

Split 2:
3 4 / 2 / 6 1 / 5

Split 3:
3 / 4 / 2 / 6 / 1 / 5

Merge of 3 / 4:
Take the 3: 3, left with: / 4
Empty list, take the rest of the other: 3 4

Merge of 6 / 1:
Take the 1: 1, left with: 6 /
Empty list, take the rest of the other: 1 6

Merge of 3 4 / 2:
Take the 2: 2, left with: 3 4 /
Empty list, take the rest of the other: 2 3 4

Merge of 1 6 / 5:
Take the 1: 1, left with: 6 / 5
Take the 5: 1 5, left with: 6 /
Empty list, take the rest of the other: 1 5 6

Merge of 2 3 4 / 1 5 6:
Take the 1: 1, left with 2 3 4 / 5 6
Take the 2: 1 2, left with 3 4 / 5 6
Take the 3: 1 2 3, left with / 5 6
Empty list, take the rest of the other: 1 2 3 4 5 6

Mergesort is one of the faster sorts. Given a list with n elements, it will take about n * log(n) steps (the log is base 2).
5. Quicksort works by choosing a pivot value and moving list elements around. Each element less than the pivot will be closer to the beginning of the list than the pivot, and each element greater than the pivot will be closer to the end of the list. By doing this operation many times with different pivots, the list will become sorted. For the fastest operation, which would be the best pivot value?

Answer: A value in the middle of the current sublist

By choosing an element whose value is in the middle of the elements in the current sublist, you are dividing the sublist into two equal portions, which gives the most efficient operation. Choosing an element at one extreme or the other will result in horrible execution time.

Here is an example that starts with two bad choices, but then uses ideal choices afterward. We will be sorting the sequence "2 6 4 3 1 5" (the * indicates the current pivot):

Start: 2 6 4 3 *1 5
1: 1 *6 4 3 2 5 (notice how only one swap was made? 1 was a bad choice)
2: 1 5 4 *3 2 6 (again, only one swap; 6 was a bad choice too)
3: 1 2 3 4 5 6 (3 was an excellent choice; both the 5 and 2, and the 3 and 4 swapped, completely ordering the list)

Quicksort is a fast sort (hence its name). It will take, on average, about n * log(n) steps to sort a list with n elements. But be careful: make too many bad pivot decisions, and the runtime will approach n * n. Oh, and you can't search for the perfect pivot either, since that too takes time and will ruin the fast nature of this algorithm.
6. Which algorithm would work best to sort data as it arrives, one piece at a time, perhaps from a network?

Answer: Insertion sort

Insertion sort is the only one out of these choices that could perform its operation with incomplete knowledge. Mergesort, quicksort, and selection sort each need to be able to move all of the elements around from the start.
7. Which of these sorting algorithms could easily be parallelized? (Given any number of extra computers to help with the task, which would require the least extra programming to have them work together to sort the list)?

Answer: Mergesort

Mergesort is ideal for parallelization, since a list is being split up and joined back together anyway. The other choices would each involve adding a merge operation to the sort, which was not present before. Since mergesort already has a merge operation built in, it is the ideal choice.
8. When would it be a good idea to use bubble sort?

Answer: As a placeholder, until you implement something else

Honestly, bubble sort is about as slow as they come, without actually *trying* to make something crawl. It should never be used in production if you do not know the size of the dataset it will be used on, since it will take so long on larger lists.
9. A 'stable' sort is a sort that will not change the relative order of any pair of equal values in a list. Which of these is (in its default implementation) *not* a stable sort?

Answer: Quicksort

Quicksort simply swaps elements around to get them on the correct side of the pivot, and there is no rule saying on which side of the pivot an element with a value equal to the pivot should go. As a result, equal elements may not be in the same relative order as they were when the sort began.
10. Which of the following sorting algorithms cannot be performed in-place (it needs scratch-space apart from the array being sorted)?

Answer: Mergesort

Mergesort needs space in which to merge the elements of its sublists. The others, however, are able to simply swap elements around within the list being sorted.
Source: Author Hegh

This quiz was reviewed by FunTrivia editor crisw before going online.
Any errors found in FunTrivia content are routinely corrected through our feedback system.
3/28/2024, Copyright 2024 FunTrivia, Inc. - Report an Error / Contact Us