Basic Sorts

Bubble Sort

Bubble sort is a simple sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

Code for bubble sort:

def bubble_sort(my_list):
    for i in range(len(my_list) - 1, 0 ,-1):
        for j in range(i):
            if my_list[j] > my_list[j+1]:
                temp = my_list[j]
                my_list[j] = my_list[j+1]
                my_list[j+1] = temp
    return my_list

print(bubble_sort([4,2,6,5,1,3]))

Selection Sort

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

Code for selection sort:

def selection_sort(my_list):
    for i in range(len(my_list)-1):
        min_index = i
        for j in range(i+1, len(my_list)):
            if my_list[j] < my_list[min_index]:
                min_index = j
        if i != min_index:
            temp = my_list[i]
            my_list[i] = my_list[min_index]
            my_list[min_index] = temp
    return my_list

print(selection_sort([4,2,6,5,1,3]))

Insertion Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

def insertion_sort(my_list):
    for i in range(1, len(my_list)):
        temp = my_list[i]
        j = i-1
        while temp < my_list[j] and j > -1:
            my_list[j+1] = my_list[j] 
            my_list[j] = temp
            j -= 1
    return my_list

print(insertion_sort([4,2,6,5,1,3]))

In the worst case, the time complexity of the above algorithm is O(n^2). In the best case (for sorted or almost sorted lists), the time complexity of the above algorithm is O(n).

Quiz: Sorting

• Bubble, Selection, and Insertion Sort all have O(n) time complexity: False. Each of these three sorting algorithms have a loop within a loop so they are O(n^2).

• Bubble, Selection, and Insertion Sort have O(1) space complexity: True. All three of these sort the list in place. That means that they do not create additional copies of the list. That means it the space complexity is O(1).

• Bubble, Selection, and Insertion Sort are all O(n) if you start with a sorted (or almost sorted) array: False. Only Insertion Sort is O(n) when you start with sorted (or almost sorted) data.