Tidying Up Some Numbers

Computer Science Level 2

$\text{Step 1: } \rightarrow \large{ \text{ [ 4, 2, 1, 5, 3 ] } } \\ \text{Step 2: } \rightarrow \large{ \text{ [ 2, 4, 1, 5, 3 ] } } \\ \text{Step 3: } \rightarrow \large{ \text{ [ 1, 2, 4, 5, 3 ] } } \\ \text{Step 4: } \rightarrow \large{ \text{ [ 1, 2, 4, 5, 3 ] } } \\ \text{Step 5: } \rightarrow \large{ \text{ [ 1, 2, 3, 4, 5 ] } }$

Which sorting technique is being used above to sort the array?

Insertion Sort Bubble Sort Merge Sort Selection Sort

1 solution

Eli Ross Staff
Feb 14, 2016

It can't be Bubble Sort , since Bubble Sort works through the list (multiple times if needed) swapping adjacent elements, yet between Step 2 and Step 3, three elements moved.

It's pretty obviously not Merge Sort , since it doesn't look as if a divide-and-conquer approach is being used. Also, the move of the 1 to the front of the list between Step 2 and 3 wouldn't happen in Merge Sort.

It can't be Selection Sort , since it looks for the smallest element in the right, unsorted part of the list and moves it into the sorted part. For example, it would bring 1 to the front of the list between Step 1 and Step 2.

That leaves Insertion Sort as the only possibility. While similar to Bubble Sort, this sort makes a sorted sublist to the left and right of some element (often the first element in the list). Here, the element being used is 4. For example, it checks that 2 is less than 4, so it gets moved to the left of the list in step 2. Then it sees that 2 is also less than 4, and puts it in a sorted sublist of [1,2] to the left of 4, and so on.

Tidying Up Some Numbers

1 solution

0 pending reports