Algorithms are well defined instructions used to solve problems. Imagine you live on the second floor of a building and you needed to give yourself instructions to check your mail. Your algorithm would look something like this:
stand_up() find_mailbox_key() take_mailbox_key() go_to_front_door() open_front_door() exit_apartment() close_front_door() go_down_stairs() go_to_front_door() open_front_door() exit_building() close_front_door() find_mailbox() unlock_mailbox_with_mailbox_key() open_maibox() check_for_mail()
Notice that we needed to be very well defined in our instructions. We cannot exit the apartment without opening the door. Omitting one instruction can prevent developers from solving a problem.
There are several different types of algorithms in python. Some of which can help solve problems more quickly than others. We measure this using the Big-O notation.
In this article, we dive into different types of sorting algorithms while measuring their efficiency, or Big-O notation.
Python Sorting Algorithms
Sorting algorithms are building block algorithms which many other algorithms can build upon. Sorting algorithms are used to solve problems like searching for an item(s) on a list, selecting an item(s) from a list, and distributions. Solving these problems is much faster with sorting.
Imagine you have a walk-in closet that is not only organized in terms of casual, active-wear, and business, but is also color coordinated. How much faster would it be to find your blue gym shorts in the list that is your closet versus an unorganized, or unsorted closet?
Python’s Built-In Sorting Algorithm
Python does have a built-in sorting algorithm, sorted(), that can be used for lists.
list = [5, 45, 22 , 3, 9, 0, 12, 6, 1] print(sorted(list)) # prints [0, 1, 3, 5, 6, 9, 12, 22, 45]
Bubble Sort
Bubble sort is the simplest, but very slow, sorting algorithm, with a Big-O notation of O(n^2). We will learn more about Big-O later. For now, let’s go through the list multiple times, comparing elements one by one, and swapping them accordingly. Take the example below.
Notice how every time we have to iterate through the list, the section of the list we need to iterate through gets smaller because the items on the right (in orange) have already been sorted. Below is an explanation of what is happening with our bubble sort visualization above.
# initial list, compare 29 & 10 [29, 10, 15, 32, 10] # 29 > 10, so we swap & compare 29 & 15 [10, 29, 15, 32, 10] # 29 > 15, so we swap & compare 29 & 32 [10, 15, 29, 32, 10] # 29 < 32, so we compare 32 & 10 [10, 15, 29, 32, 10] # 32 > 10, so we swap [10, 15, 29, 10, 32] # Begin again from the first element, compare 10 & 15 [10, 15, 29, 10, 32] # 10 < 15, so we compare 15 & 29 [10, 15, 29, 10, 32] # 15 < 29, so we compare 29 & 10 [10, 15, 29, 10, 32] # 29 > 15, so we swap & compare 29 & 32 [10, 15, 10, 29, 32] # Begin again, from the first element compare 10 & 15 [10, 15, 10, 29, 32] # 10 < 15, so we compare 15 & 10 [10, 15, 10, 29, 32] # 15 > 10, so we swap [10, 10, 15, 29, 32] # Begin again from the first element, list is now sorted [10, 10, 15, 29, 32]
The code for bubble sort would like something like the below example code:
def bubble_sort(list):
# Traverse (travel across) through every element on the list
for i in range(0, len(list) - 1):
# Compare each item in list 1 by 1. Comparison in each iteration
# will shorten as the last elements become sorted
for j in range(0, len(list) - 1 - i):
# traverse the list from 0 to n-i-1
# if the element found is greater than the next element, swap
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
return list
print(bubble_sort([2, 3, 7, 1, 9, 5]))Insertion Sort
If you have ever played poker, you most likely have used this sorting method. With the insertion sort, you would begin with one card in your hand, pick the next random card, insert it in the correct sorted order, and repeat.
Insertion sort’s algorithm runs in O(n) time, best case, and O(n^2) worst case.
Below is an explanation of the insertion sort algorithm visualization above.
# Mark the first element, 10, as sorted [10, 3, 2, 6] # Look at next element, 3, 3 < 10 [10, 3, 2, 6] # Extract 3 and move it before 10, mark first element, 3 as sorted [3, 10, 2, 6] # Look at the next unsorted element, 2, 2 < 10, 2 < 3 [3, 10, 2, 6] # Extract 2 and move it before 3, mark first element, 2, as sorted [2, 3, 10, 6] # Look at the next unsorted element, 6, 6 < 10, 6 > 3 [2, 3, 10, 6] # Extract 6 and move it before 10 [2, 3, 6, 10]
Below is a code example of the insertion sort algorithm.
def insertionSort(list):
# all the values after the first
index_length = range(1, len(list))
# to do an operation on all these values
# for all the value is the index_length value,
for i in index_length:
# we want to sort those values
sort = list[i]
# while the item to the left is greater than the item
# to the right
# notice that we also have to write i > 0 bc python allows
# for negative indexing
while list[i-1] > sort and i > 0:
# swap
list[i], list[i-1] = list[i-1], list[i]
# to continue doing comparisons down the list,
# look at the next item
i = i - 1
return list
print(insertionSort([7, 3, 4, 1, 9]))Merge Sort
Merge sort has a divide and conquer approach to sorting, and is a recursive sorting algorithm, different from the ones above which are iterative. To understand merge sort, we must first understand recursion.
Recursive functions are functions that call themselves, but have a base case to work towards to prevent infinite loops. Below is a code example of a basic recursive function.
def recursive(n):
# This is the base case we are working towards
# When we get to where n==0, we return 1
if n == 0:
return 1
# here we move towards the base case
return n * recursive(n - 1)In merge sort, we begin sorting pair by pair until everything is in order and we are able to merge. Take the visualization below.
Step 1
First we compare the first two indexes and sort them, before we move on to the next two.
Step 2
Second, we begin by comparing the first index of the first two groups, sorting along the way, before we move right again.
Step 3
Lastly, we move across the indexes of the two groups, comparing and sorting the values before we move right.
Below is a code example of merge sort.
# bc there are multiple steps in the divide and conquer approach
# we need multiple function definitions
# helper function
def merge(left, right):
elements = len(left) + len(right)
merged_list = [0] * elements
left_pointer = 0
right_pointer = 0
i = 0
# while there are elements in either list
while left_pointer < len(left) or right_pointer < len(right):
# if there are elements in both lists
if left_pointer < len(left) and right_pointer < len(right):
if left[left_pointer] < right[right_pointer]:
merged_list[i] = left[left_pointer]
left_pointer += 1
else:
merged_list[i] = right[right_pointer]
right_pointer += 1
i += 1
# if there are only elements in the left list
elif left_pointer < len(left):
merged_list[i] = left[left_pointer]
left_pointer += 1
i += 1
# if there are only elements in the right list
elif right_pointer < len(right):
merged_list[i] = right[right_pointer]
right_pointer += 1
i += 1
return merged_list
# sort function
def merge_sort(list):
if len(list) <= 1:
return list
else:
mid = (len(list)) // 2
left_array = list[:mid]
right_array = list[mid:]
left_array = merge_sort(left_array)
right_array = merge_sort(right_array)
result = merge(left_array, right_array)
return result
# in-place merge sort algorithm
def merge_in_place(list, begin, mid, end):
begin_high = mid + 1
# if mid and begin_high are already in order, return
if list[mid] <= list[begin_high]:
return
# while pointers are within bounds
while begin <= mid and begin_high <= end:
# if begin element is in order w/ respect to begin_high element
if list[begin] <= list[begin_high]:
# increment begin
begin += 1
else:
# current value is at begin of begin_high
value = list[begin_high]
# index is begin_high
index = begin_high
# while index is not equal to begin
while index != begin:
# swap item at index with it's left-neighbor
list[index] = list[index-1]
# decrement index
index -= 1
# value at list begin is new value
list[begin] = value
# increment all pointers (minus end)
begin += 1
mid += 1
begin_high += 1
# sorting in place
def merge_sort_in_place(list, left, right):
if left < right:
mid = (left + right) // 2
merge_sort_in_place(list, left, mid)
merge_sort_in_place(list, mid+1, right)
merge_in_place(list, left, mid, right)
return list
list = [6, 3, 1, 4, 8, 2, 5, 7]
result = merge_sort_in_place(list, 0, len(list)-1)
print(result)Since we must divide and then conquer with merge sort, we can think of its runtime complexity as O(log(n)) * O(n) or O(n * log(n)). For additional information on Big O notation, check out the Career Karma articles, Big-O Notation Time and Big-O Notation Space.
About us: Career Karma is a platform designed to help job seekers find, research, and connect with job training programs to advance their careers. Learn about the CK publication.
