Sorting Algorithms
Sorting is a basic building block that many other algorithms are built upon. It’s related to several exciting ideas that you’ll see throughout your programming career. Understanding how sorting algorithms in Python work behind the scenes is a fundamental step toward implementing correct and efficient algorithms that solve real-world problems.
Python’s Built-In Sorting Algorithms
sorted()
Basic Usage
numbers = [6, 9, 3, 1]
numbers_tuple = (6, 9, 3, 1)
numbers_set = {5, 5, 10, 1, 0}
string_number_value = '34521'
string_value = 'I like to sort'
numbers_sorted = sorted(numbers)
# numbers_sorted
# [1, 3, 6, 9]
numbers_tuple_sorted = sorted(numbers_tuple)
# numbers_tuple_sorted
# [1, 3, 6, 9]
numbers_set_sorted = sorted(numbers_set)
# numbers_set_sorted
# [0, 1, 5, 10]
sorted_string_number = sorted(string_number_value)
# sorted_string_number
# ['1', '2', '3', '4', '5']
sorted_string = sorted(string_value)
# sorted_string
# [' ', ' ', ' ', 'I', 'e', 'i', 'k', 'l', 'o', 'o', 'r', 's', 't', 't']
Bubble Sort
Since this implementation sorts the array in ascending order, each step “bubbles” the largest element to the end of the array. This means that each iteration takes fewer steps than the previous iteration because a continuously larger portion of the array is sorted.
def bubble_sort(array):
n = len(array)
for i in range(n):
# Create a flag that will allow the function to
# terminate early if there's nothing left to sort
already_sorted = True
# Start looking at each item of the list one by one,
# comparing it with its adjacent value. With each
# iteration, the portion of the array that you look at
# shrinks because the remaining items have already been
# sorted.
for j in range(n - i - 1):
if array[j] > array[j + 1]:
# If the item you're looking at is greater than its
# adjacent value, then swap them
array[j], array[j + 1] = array[j + 1], array[j]
# Since you had to swap two elements,
# set the `already_sorted` flag to `False` so the
# algorithm doesn't finish prematurely
already_sorted = False
# If there were no swaps during the last iteration,
# the array is already sorted, and you can terminate
if already_sorted:
break
return array
Insertion Sort
Like bubble sort, the insertion sort algorithm is straightforward to implement and understand. But unlike bubble sort, it builds the sorted list one element at a time by comparing each item with the rest of the list and inserting it into its correct position. This “insertion” procedure gives the algorithm its name.
An excellent analogy to explain insertion sort is the way you would sort a deck of cards. Imagine that you’re holding a group of cards in your hands, and you want to arrange them in order. You’d start by comparing a single card step by step with the rest of the cards until you find its correct position. At that point, you’d insert the card in the correct location and start over with a new card, repeating until all the cards in your hand were sorted.
def insertion_sort(array):
# Loop from the second element of the array until
# the last element
for i in range(1, len(array)):
# This is the element we want to position in its
# correct place
key_item = array[i]
# Initialize the variable that will be used to
# find the correct position of the element referenced
# by `key_item`
j = i - 1
# Run through the list of items (the left
# portion of the array) and find the correct position
# of the element referenced by `key_item`. Do this only
# if `key_item` is smaller than its adjacent values.
while j >= 0 and array[j] > key_item:
# Shift the value one position to the left
# and reposition j to point to the next element
# (from right to left)
array[j + 1] = array[j]
j -= 1
# When you finish shifting the elements, you can position
# `key_item` in its correct location
array[j + 1] = key_item
return array
Merge Sort
Merge sort is a very efficient sorting algorithm. It’s based on the divide-and-conquer approach, a powerful algorithmic technique used to solve complex problems.
To properly understand divide and conquer, you should first understand the concept of recursion. Recursion involves breaking a problem down into smaller subproblems until they’re small enough to manage. In programming, recursion is usually expressed by a function calling itself.
def merge(left, right):
# If the first array is empty, then nothing needs
# to be merged, and you can return the second array as the result
if len(left) == 0:
return right
# If the second array is empty, then nothing needs
# to be merged, and you can return the first array as the result
if len(right) == 0:
return left
result = []
index_left = index_right = 0
# Now go through both arrays until all the elements
# make it into the resultant array
while len(result) < len(left) + len(right):
# The elements need to be sorted to add them to the
# resultant array, so you need to decide whether to get
# the next element from the first or the second array
if left[index_left] <= right[index_right]:
result.append(left[index_left])
index_left += 1
else:
result.append(right[index_right])
index_right += 1
# If you reach the end of either array, then you can
# add the remaining elements from the other array to
# the result and break the loop
if index_right == len(right):
result += left[index_left:]
break
if index_left == len(left):
result += right[index_right:]
break
return result
QuickSort
Just like merge sort, the Quicksort algorithm applies the divide-and-conquer principle to divide the input array into two lists, the first with small items and the second with large items. The algorithm then sorts both lists recursively until the resultant list is completely sorted.
Dividing the input list is referred to as partitioning the list. Quicksort first selects a pivot element and partitions the list around the pivot, putting every smaller element into a low array and every larger element into a high array.
Putting every element from the low list to the left of the pivot and every element from the high list to the right positions the pivot precisely where it needs to be in the final sorted list. This means that the function can now recursively apply the same procedure to low and then high until the entire list is sorted.
from random import randint
def quicksort(array):
# If the input array contains fewer than two elements,
# then return it as the result of the function
if len(array) < 2:
return array
low, same, high = [], [], []
# Select your `pivot` element randomly
pivot = array[randint(0, len(array) - 1)]
for item in array:
# Elements that are smaller than the `pivot` go to
# the `low` list. Elements that are larger than
# `pivot` go to the `high` list. Elements that are
# equal to `pivot` go to the `same` list.
if item < pivot:
low.append(item)
elif item == pivot:
same.append(item)
elif item > pivot:
high.append(item)
# The final result combines the sorted `low` list
# with the `same` list and the sorted `high` list
return quicksort(low) + same + quicksort(high)
Timsort
The Timsort algorithm is considered a hybrid sorting algorithm because it employs a best-of-both-worlds combination of insertion sort and merge sort. Timsort is near and dear to the Python community because it was created by Tim Peters in 2002 to be used as the standard sorting algorithm of the Python language.
The main characteristic of Timsort is that it takes advantage of already-sorted elements that exist in most real-world datasets. These are called natural runs. The algorithm then iterates over the list, collecting the elements into runs and merging them into a single sorted list.
def insertion_sort(array, left=0, right=None):
if right is None:
right = len(array) - 1
# Loop from the element indicated by
# `left` until the element indicated by `right`
for i in range(left + 1, right + 1):
# This is the element we want to position in its
# correct place
key_item = array[i]
# Initialize the variable that will be used to
# find the correct position of the element referenced
# by `key_item`
j = i - 1
# Run through the list of items (the left
# portion of the array) and find the correct position
# of the element referenced by `key_item`. Do this only
# if the `key_item` is smaller than its adjacent values.
while j >= left and array[j] > key_item:
# Shift the value one position to the left
# and reposition `j` to point to the next element
# (from right to left)
array[j + 1] = array[j]
j -= 1
# When you finish shifting the elements, position
# the `key_item` in its correct location
array[j + 1] = key_item
return array