What sorting algorithm performs these steps?

Question

It was a multiple choice question on the exam today, and (at least) one of the answers should be true, but to me they all look wrong.

Sorting steps:
5 2 6 1 3 4
4 2 6 1 3 5
4 2 5 1 3 6
4 2 3 1 5 6
1 2 3 4 5 6

The available answers were: Bubble Sort, Insert Sort, Sort Select, Sort Sort, and Quick Sort.

Answer 1

None of them.

• bubble sorting: no. After k steps, the last k elements must be k largest, sorted.
• inserting sorting: no. After k steps, k first elements should be sorted.
• selection sort: no. After k steps, k first elements should be the smallest, sorted.
• merge sort: no. After k steps, the value can only move 2^k - 1 places. (5 moves 5 places with k = 1)
• quick sort: no. Regardless of the pivot point, 1 and 6 are extreme values, they can remain in this starting position.

In quicksort: to make it clear that this is not possible, let's list the results of each rotation for the first step:

• 5: [2134] - 5 - [6] . (2134 may be in any order)
• 2: [1] - 2 - [5634]
• 6: [52134] - 6
• 1: 1 - [52634]
• 3: [21] - 3 - [564]
• 4: [213] - 4 - [56]

The obvious way to see that all of these elements are incompatible with the OP output is that in each case 1 is in front of 6 , regardless of how you implement the reference element or section.

Answer 2

I think this is Quick sort. Here we can see the following steps:

• Random selection of a reference element in an array (pivotValue) with respect to which array elements are reordered.

• Move all the values ​​that are larger than the link to the right, and all the values ​​remaining below.

• Repeat the algorithm to unsort the left and right parts of the array, while each element will not be displayed in its position

Why do I think so:

This is definitely not a Bubble Sort, because it compares the first two elements of the array, so the first step should be 2 5 6 1 3 4

This is not an insertion sort, because it is a sequential algorithm. In the first step, we see that we compared the first and last elements

This is not a sort of selection, because it finds the lowest value and moves it up, so the first step should be 1 5 2 6 3 4

This is not Merge sorting because the array is split into two subarrays. In this case, we see the interaction of the "first" and "second" parts

Answer 3

To solve all this, you need to make a function for each sorting algorithm, but include an instruction to print the array after each swap. Then apply your print sorting algorithms to the original array [5 2 6 1 3 4] and see which sorting method produces the same output. In addition, it helps you compare all the different methods.