Bootcamp

Search…

A.10: Sorting Algorithms

This module explores various ways to sort unsorted arrays of numbers. While our examples only use numbers, the same methods can be used to sort arrays of arbitrary data types according to arbitrary sort order.

We will rarely write sorting algorithms as software engineers because most languages have built-in sorting functions, and DS&A interview questions rarely test sorting algorithms because sorting algorithms are relatively easily memorised. However, we will learn sorting algorithms because they are a common-enough concept in DS&A and the strategies behind sorting algorithms can be relevant to how we approach other DS&A problems.

There is no need to memorise the below sorting algorithms' implementation. Just understand how they work such that you could describe their logic well-enough to write pseudocode.

- Runtime:
*O(n²)* - Space:
*O(1)* - Sort In-Place: Yes
- Stable: No

- good space complexity
- simple code
- slow for large lists / fast for small lists

for each element in the array

consider the current element as the least value

for each element in the rest of the array forward from the current element

look for an element that is less

if it's less, set the inner loop element as the least value

swap the least value and the current element

from pprint import pprint

A = [64, 25, 12, 22, 11]

def selection_sort(arr):

# traverse through all array elements

for outer_idx in range(len(arr)):

# given current point in array

# mark that value as min

min_idx = outer_idx

# start inner loop

# loop starting at outer_idx to end

for i in range(outer_idx+1, len(arr)):

# if a lower value is found

if arr[min_idx] > arr[i]:

min_idx = i

# loop set a min value

# swap the found minimum element with

# the first element

arr[outer_idx], arr[min_idx] = arr[min_idx], arr[outer_idx]

return arr

result = selection_sort(A)

print ("Sorted array")

pprint(result)

from pprint import pprint

A = [64, 25, 12, 22, 11]

def selection_sort(arr):

# Traverse through all array elements

for outer_idx in range(len(arr)):

# given current point in array

# mark that value as min

min_idx = outer_idx

print(f'set min value for location: {outer_idx} : {arr[outer_idx]}')

# start inner loop

# loop starting at outer_idx to end

print('starting inner loop')

for i in range(outer_idx+1, len(arr)):

# if a lower value is found

if arr[min_idx] > arr[i]:

print(f'found a lower value: {arr[i]}')

min_idx = i

print('*******************')

# loop set a min value

# swap the found minimum element with

# the first element

print(f'swapping {arr[outer_idx]} with {arr[min_idx]}')

arr[outer_idx], arr[min_idx] = arr[min_idx], arr[outer_idx]

print('done with outer loop')

print('-------------------')

return arr

result = selection_sort(A)

print ("Sorted array")

pprint( result)

- Runtime:
*O(n²)* - Space:
*O(1)* - Sort In-Place: Yes
- Stable: Yes

- good space complexity
- simple code
- slow for large lists / fast for small lists
- good for nearly sorted lists - will exit early if list is done ("adaptive")
- can sort while new items are being added to list ("online")

begin with the second element

for each element in the array, starting with the second element

consider the current element as "removed"

look backwards through the array starting from the current element

if the current element is more than the inner loop value

move the current element into the inner loop location

if the inner loop element is less than the current element, end the loop

from pprint import pprint

A = [64, 25, 12, 22, 11]

def insertion_sort(arr):

# Traverse through the array starting with the 2nd element

for i in range(1, len(arr)):

# set the current element as key

key = arr[i]

# look backwards through the array

# move every value forward by one until it finds

# a value smaller than key

j = i-1

while j >= 0 and key < arr[j] :

# move j ahead one

arr[j + 1] = arr[j]

j -= 1

# put key in the space we found using the loop

arr[j + 1] = key

return arr

result = insertion_sort(A)

print ("Sorted array")

pprint( result)

from pprint import pprint

A = [64, 25, 12, 22, 11]

def insertion_sort(arr):

# Traverse through the array starting with the 2nd element

for i in range(1, len(arr)):

print('****************************')

# set the current element as key

key = arr[i]

print(f'removed: {key}')

# look backwards through the array

# move every value forward by one until it finds

# a value smaller than key

print('looking back ')

j = i-1

while j >= 0 and key < arr[j] :

# move j ahead one

print(f'putting {arr[j]} at: {j+1}')

arr[j + 1] = arr[j]

j -= 1

# put key in the space we found using the loop

print(f'putting *key* {key} at: {j+1}')

arr[j + 1] = key

return arr

result = insertion_sort(A)

print ("Sorted array")

pprint( result)

- Runtime:
*O(n²)* - Space:
*O(1)* - Sort In-Place: Yes
- Stable: Yes

- good space complexity
- simple code
- slow for large lists / fast for small lists

Bubble sort is considered the "beginner's" sorting algorithm. It is slow and lacks the features of other naive algorithms. However, the pseudocode is simple and so it is used to introduce concepts of sorting algorithms.

for each element in an array

starting with the current element and

look at all elements after it

compare the inner element with it's neighbor

if the inner elemnt is larger

swap them

from pprint import pprint

A = [64, 25, 12, 22, 11]

def bubble_sort(arr):

# Traverse through the array

for i in range(len(arr)):

# loop to compare array elements

for j in range(0, len(arr) - i - 1):

# compare two adjacent elements

# change > to < to sort in descending order

if arr[j] > arr[j + 1]:

# swapping elements if elements

# are not in the intended order

temp = arr[j]

arr[j] = arr[j+1]

arr[j+1] = temp

return arr

result = bubble_sort(A)

print ("Sorted array")

pprint( result)

from pprint import pprint

A = [64, 25, 12, 22, 11]

def bubble_sort(arr):

# Traverse through the array

for i in range(len(arr)):

print('***************************')

print(f'at: {i}')

# loop to compare array elements

for j in range(0, len(arr) - i - 1):

# compare two adjacent elements

# change > to < to sort in descending order

print(f'comparing: {j} to {j+1} {arr}')

if arr[j] > arr[j + 1]:

print(f'its larger, swapping : {arr[j]} to {arr[j+1]}')

# swapping elements if elements

# are not in the intended order

temp = arr[j]

arr[j] = arr[j+1]

arr[j+1] = temp

return arr

result = bubble_sort(A)

print ("Sorted array")

pprint( result)

The main difference is that insertion sort finds an element's place *in the already sorted list*, and bubble sort does not. This behavior is why insertion sort is "online" and new unsorted things can be added to the end of the array.

Last modified 4mo ago

Copy link

On this page

Introduction

Naive Sorting Algorithms

Selection Sort

Insertion Sort

Bubble Sort