Sorting Trivia Quiz

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.

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.

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.

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).

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.

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.

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.

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.

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.

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.