Sorting Algorithm output at end of pass 3-CodePudding

Given the following initially unsorted list:

[77, 101, 40, 43, 81, 129, 85, 144]

Which sorting algorithm produces the following list at the end of Pass Number 3? Is it Bubble, Insertion or Selection?

[40, 43, 77, 81, 85, 101, 129, 144]

Can someone give me a clue on how I can solve this please.

CodePudding user response：

Insertion sort:

def insertion_sort(array):
    for i in range(1, len(array)):
        key_item = array[i]
        j = i - 1
        while j >= 0 and array[j] > key_item:
            array[j   1] = array[j]
            j -= 1
        array[j   1] = key_item
        print("Step",i,":",array)
    return array

data=[77, 101, 40, 43, 81, 129, 85, 144]
insertion_sort(data)

Output:

Step 1 : [77, 101, 40, 43, 81, 129, 85, 144]
Step 2 : [40, 77, 101, 43, 81, 129, 85, 144]
Step 3 : [40, 43, 77, 101, 81, 129, 85, 144]
Step 4 : [40, 43, 77, 81, 101, 129, 85, 144]
Step 5 : [40, 43, 77, 81, 101, 129, 85, 144]
Step 6 : [40, 43, 77, 81, 85, 101, 129, 144]
Step 7 : [40, 43, 77, 81, 85, 101, 129, 144]

Bubble sort:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        already_sorted = True
        for j in range(n - i - 1):
            if array[j] > array[j   1]:
                array[j], array[j   1] = array[j   1], array[j]
                already_sorted = False
        if already_sorted:
            break
        print("Step:",n-j-1)
        print(array)
    return array

data = [77, 101, 40, 43, 81, 129, 85, 144]
bubble_sort(data)

Output:

Step: 1
[77, 40, 43, 81, 101, 85, 129, 144]
Step: 2
[40, 43, 77, 81, 85, 101, 129, 144]

Selection Sort:

def selectionSort(array, size):
    for step in range(size):
        min_idx = step

        for i in range(step   1, size):
            if array[i] < array[min_idx]:
                min_idx = i
        (array[step], array[min_idx]) = (array[min_idx], array[step])
        print("step",step 1,":",end="")

        print(array)

data = [77, 101, 40, 43, 81, 129, 85, 144]
size = len(data)
selectionSort(data, size)

Output:

step 1 :[40, 101, 77, 43, 81, 129, 85, 144]
step 2 :[40, 43, 77, 101, 81, 129, 85, 144]
step 3 :[40, 43, 77, 101, 81, 129, 85, 144]
step 4 :[40, 43, 77, 81, 101, 129, 85, 144]
step 5 :[40, 43, 77, 81, 85, 129, 101, 144]
step 6 :[40, 43, 77, 81, 85, 101, 129, 144]
step 7 :[40, 43, 77, 81, 85, 101, 129, 144]
step 8 :[40, 43, 77, 81, 85, 101, 129, 144]

You can also get more guidelines from the link below how to run algorithms: https://realpython.com/sorting-algorithms-python/

CodePudding user response：

Insertion sort would change the relative order of at most 3 items in 3 passes resulting in the first 3 items being in order and the rest unchanged. Selection sort would affect only the positions of the first 3 items and the 3 smallest (or greatest) items. Only the bubble sort would swap other items around. The movements of 40 and 129 is a telltale sign that points to a Bubble sort.

Note that this may be a trick question because all numbers that need to be shifted are at most 2 positions off except 2 of them (101 & 129 which are the 2nd and 3rd largest and would end up in their right places after 2 passes). A properly implemented Bubble sort would not get to a 3rd pass. So the answer could be "none of them"