# 6.3 Sorting Algorithms Flashcards

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

Bubble sort

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

Insertion sort

How do you merge 2 sorted lists?

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

Give examples of sorting algorithms

Bubble

Insertion

Merge

Bubble sort process

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

Insertion sort process

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

Merge 2 sorted lists process

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

Merge sort process

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

Give the order of fastest sorting algorithms

1) Merge

2) Insertion

3) Bubble