Sorting Algorithms Flashcards

All 13 cards in this deck

What are the main steps of a bubble sort?
e.g. sort 3, 1, 2

1. Compare the first pair and swap them if they are in the wrong order: 1, 3, 2.
2. Move along one place and repeat to the end of the list (one pass): 1, 2, 3.
3. Repeat passes until a pass makes no swaps: list is sorted as 1, 2, 3.

What are the main steps of a merge sort?
e.g. sort 4, 1, 3, 2

1. Split the list in half repeatedly until each list holds one item: 4 | 1 | 3 | 2.
2. Merge pairs of lists, comparing values so each merged list is in order: 1, 4 and 2, 3.
3. Keep merging until one list remains: 1, 2, 3, 4.

Which sorting algorithm splits the data into individual items before recombining them in order?

Merge sort.

True or false? A bubble sort always swaps the pair of values it compares.

False. It swaps them only if they are in the wrong order.

Give two advantages of a merge sort over a bubble sort.

It takes much less time to sort large lists, and its running time stays about the same however the items were ordered to begin with.

Why does a bubble sort need less memory than a merge sort?

A bubble sort rearranges the items within the original list, whereas a merge sort creates extra sub-lists as it splits and merges.

A list is already in order. Which takes less time to sort it: a merge sort, or a bubble sort that stops after a pass with no swaps?

The bubble sort. It makes one pass, finds no swaps and stops, whereas a merge sort still splits and merges every item.

Why is a merge sort efficient?

Very short lists are trivial to sort, and combining two lists that are already in order takes few comparisons.

In a bubble sort into ascending order, where does the largest value end up after the first pass?

At the end of the list, in its final position, so each later pass can stop one item sooner.

In a merge sort, how are two ordered sub-lists merged into one?

Compare the first remaining item of each sub-list, move the smaller one into the new list, and repeat until every item has been moved.

In a bubble sort, why is a temp variable used when two values are swapped?

It holds a copy of the first value; otherwise that value would be overwritten and lost when the second value is copied into its place.

An algorithm has nested FOR loops that compare arr[j] with arr[j + 1] and swap them if they are in the wrong order. Which algorithm is it?

A bubble sort. Its purpose is to sort the array into order.

Apart from using less memory and being quicker on a list that is already in order, give one advantage of a bubble sort over a merge sort.

It is simpler to write and understand.