6.3 Sorting Algorithms

Question 1

What sorting algorithm is this? (Written in python)

def sort(lst: list):
    counter = 0
    for i in range(len(lst) - 1):
        while counter != len(lst) - 1:
            if lst[counter + 1] < lst[counter]:
                lst[counter], lst[counter + 1] = lst[counter + 1], lst[counter]
                print(lst)
            counter += 1
        counter = 0
    return lst

Answer 1

Bubble sort

Question 2

What sorting algorithm is this? (Written in python)

def sort(lst: list):
    for i in range(len(lst)):
        x = lst[i]
        for j in (lst[:i]):
            if j > x:
                lst[i+1], lst[i] = lst[i], lst[i+1]
    return lst

Answer 2

Insertion sort

Question 3

How do you merge 2 sorted lists?

Answer 3

Merge 2 sorted lists:
def merge_two_sorted_lists(lst1: list, lst2: list):
    # only works if both lists are same length
    counter = 0
    output = []
    while counter < len(lst1):
        if lst1[counter] < lst2[counter]:
            output.append(lst1[counter])
            output.append(lst2[counter])
        else:
            output.append(lst2[counter])
            output.append(lst1[counter])
        counter += 1
    return output

Question 4

Give examples of sorting algorithms

Answer 4

Bubble
Insertion
Merge

Question 5

Bubble sort process

Answer 5

Start with left most item
Compare it with item next to it
If the left node is greater than the right node, then swap them
Repeat the above 2 steps with all the items in the list
At the end of one pass throughthe list, the largest item is at the end of the list
Repeat all above steps until the items are sorted

Question 6

Insertion sort process

Answer 6

It sorts one data item at a time
Process:
One item is taken from a list and placed in the correct position
This is repeated until there are no more unsorted items in the list

Question 7

Merge 2 sorted lists process

Answer 7

Read items from list A; read items from list B
Write smaller to output list, then the larger
Move to the next node
Repeat untill there are no items in the original list

Question 8

Merge sort process

Answer 8

Divide the unsorted list into 2
Continue to divide the list until there is just one item left in the list
While merging the lists back together, sort the lists

Question 9

Give the order of fastest sorting algorithms

Answer 9

1) Merge
2) Insertion
3) Bubble