A.10: Sorting Algorithms

Introduction
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.
Naive Sorting Algorithms
Selection Sort
Runtime: O(n²)
Space: O(1)
Sort In-Place: Yes
Stable: No
Attributes
good space complexity
simple code
slow for large lists / fast for small lists
Selection Sort Pseudo Code
1
for each element in the array
2
  consider the current element as the least value
3
  for each element in the rest of the array forward from the current element
4
    look for an element that is less
5
      if it's less, set the inner loop element as the least value
6
  swap the least value and the current element
Copied!
Selection Sort
1
from pprint import pprint
2
​
3
A = [64, 25, 12, 22, 11]
4
​
5
def selection_sort(arr):
6
​
7
    # traverse through all array elements
8
    for outer_idx in range(len(arr)):
9
​
10
        # given current point in array
11
        # mark that value as min
12
        min_idx = outer_idx
13
​
14
        # start inner loop
15
        # loop starting at outer_idx to end
16
        for i in range(outer_idx+1, len(arr)):
17
​
18
            # if a lower value is found
19
            if arr[min_idx] > arr[i]:
20
                min_idx = i
21
​
22
        # loop set a min value
23
        # swap the found minimum element with
24
        # the first element
25
        arr[outer_idx], arr[min_idx] = arr[min_idx], arr[outer_idx]
26
    return arr
27
​
28
result = selection_sort(A)
29
print ("Sorted array")
30
pprint( result)
Copied!
Selection Sort with Prints
1
from pprint import pprint
2
​
3
A = [64, 25, 12, 22, 11]
4
​
5
def selection_sort(arr):
6
​
7
    # Traverse through all array elements
8
    for outer_idx in range(len(arr)):
9
​
10
        # given current point in array
11
        # mark that value as min
12
        min_idx = outer_idx
13
        print(f'set min value for location: {outer_idx} : {arr[outer_idx]}')
14
​
15
        # start inner loop
16
        # loop starting at outer_idx to end
17
        print('starting inner loop')
18
        for i in range(outer_idx+1, len(arr)):
19
​
20
            # if a lower value is found
21
            if arr[min_idx] > arr[i]:
22
                print(f'found a lower value: {arr[i]}')
23
                min_idx = i
24
​
25
            print('*******************')
26
​
27
        # loop set a min value
28
        # swap the found minimum element with
29
        # the first element
30
        print(f'swapping {arr[outer_idx]} with {arr[min_idx]}')
31
        arr[outer_idx], arr[min_idx] = arr[min_idx], arr[outer_idx]
32
        print('done with outer loop')
33
        print('-------------------')
34
    return arr
35
​
36
result = selection_sort(A)
37
print ("Sorted array")
38
pprint( result)
Copied!
Further Reading
​https://www.algostructure.com/sorting/selectionsort.php​
​https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/visualize/​
​https://www.programiz.com/dsa/selection-sort​
​https://www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm​
​https://en.wikipedia.org/wiki/Insertion_sort​
Insertion Sort
Runtime: O(n²)
Space: O(1)
Sort In-Place: Yes
Stable: Yes
Attributes
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")
Insertion Sort Pseudo Code
1
begin with the second element
2
for each element in the array, starting with the second element
3
  consider the current element as "removed"
4
  look backwards through the array starting from the current element
5
    if the current element is more than the inner loop value
6
      move the current element into the inner loop location
7
    if the inner loop element is less than the current element, end the loop
Copied!
Insertion Sort
1
from pprint import pprint
2
​
3
A = [64, 25, 12, 22, 11]
4
​
5
def insertion_sort(arr):
6
​
7
    # Traverse through the array starting with the 2nd element
8
    for i in range(1, len(arr)):
9
​
10
        # set the current element as key
11
        key = arr[i]
12
​
13
        # look backwards through the array
14
        # move every value forward by one until it finds
15
        # a value smaller than key
16
        j = i-1
17
        while j >= 0 and key < arr[j] :
18
                # move j ahead one
19
                arr[j + 1] = arr[j]
20
                j -= 1
21
        # put key in the space we found using the loop
22
        arr[j + 1] = key
23
​
24
    return arr
25
​
26
result = insertion_sort(A)
27
print ("Sorted array")
28
pprint( result)
Copied!
Insertion Sort with Prints
1
from pprint import pprint
2
​
3
A = [64, 25, 12, 22, 11]
4
​
5
def insertion_sort(arr):
6
​
7
    # Traverse through the array starting with the 2nd element
8
    for i in range(1, len(arr)):
9
​
10
        print('****************************')
11
        # set the current element as key
12
        key = arr[i]
13
        print(f'removed: {key}')
14
​
15
        # look backwards through the array
16
        # move every value forward by one until it finds
17
        # a value smaller than key
18
        print('looking back ')
19
        j = i-1
20
        while j >= 0 and key < arr[j] :
21
                # move j ahead one
22
                print(f'putting {arr[j]} at: {j+1}')
23
                arr[j + 1] = arr[j]
24
                j -= 1
25
        # put key in the space we found using the loop
26
        print(f'putting *key* {key} at: {j+1}')
27
        arr[j + 1] = key
28
​
29
    return arr
30
​
31
result = insertion_sort(A)
32
print ("Sorted array")
33
pprint( result)
Copied!
Further Reading
​https://www.algostructure.com/sorting/insertionsort.php​
​https://www.hackerearth.com/practice/algorithms/sorting/insertion-sort/visualize/​
​https://www.programiz.com/dsa/insertion-sort​
​https://www.geeksforgeeks.org/insertion-sort/​
Bubble Sort
Runtime: O(n²)
Space: O(1)
Sort In-Place: Yes
Stable: Yes
Attributes
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.
Bubble Sort Pseudo Code
1
for each element in an array
2
  starting with the current element and
3
  look at all elements after it
4
    compare the inner element with it's neighbor
5
    if the inner elemnt is larger
6
      swap them
Copied!
Bubble Sort
1
from pprint import pprint
2
​
3
A = [64, 25, 12, 22, 11]
4
​
5
def bubble_sort(arr):
6
​
7
    # Traverse through the array
8
    for i in range(len(arr)):
9
​
10
        # loop to compare array elements
11
        for j in range(0, len(arr) - i - 1):
12
​
13
            # compare two adjacent elements
14
            # change > to < to sort in descending order
15
            if arr[j] > arr[j + 1]:
16
​
17
                # swapping elements if elements
18
                # are not in the intended order
19
                temp = arr[j]
20
                arr[j] = arr[j+1]
21
                arr[j+1] = temp
22
​
23
    return arr
24
​
25
result = bubble_sort(A)
26
print ("Sorted array")
27
pprint( result)
Copied!
Bubble Sort with Print
1
from pprint import pprint
2
​
3
A = [64, 25, 12, 22, 11]
4
​
5
def bubble_sort(arr):
6
​
7
    # Traverse through the array
8
    for i in range(len(arr)):
9
​
10
        print('***************************')
11
        print(f'at: {i}')
12
        # loop to compare array elements
13
        for j in range(0, len(arr) - i - 1):
14
​
15
            # compare two adjacent elements
16
            # change > to < to sort in descending order
17
            print(f'comparing: {j} to {j+1} {arr}')
18
            if arr[j] > arr[j + 1]:
19
​
20
                print(f'its larger, swapping : {arr[j]} to {arr[j+1]}')
21
                # swapping elements if elements
22
                # are not in the intended order
23
                temp = arr[j]
24
                arr[j] = arr[j+1]
25
                arr[j+1] = temp
26
​
27
    return arr
28
​
29
result = bubble_sort(A)
30
print ("Sorted array")
31
pprint( result)
Copied!
What's the Difference Between Insetion Sort and Bubble Sort?
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.
See more here: https://stackoverflow.com/a/17271911/271932​
Further Reading
​https://www.algostructure.com/sorting/bubblesort.php​
​https://www.hackerearth.com/practice/algorithms/sorting/bubble-sort/visualize/​
​https://www.programiz.com/dsa/bubble-sort​
​https://www.geeksforgeeks.org/bubble-sort/​
​https://en.wikipedia.org/wiki/Bubble_sort​

A.9.1: Recursive Backtracking

A.10.1: Divide and Conquer Sorting

Last modified 2mo ago

Copy link

Contents

Introduction

Naive Sorting Algorithms

Selection Sort

Insertion Sort

Bubble Sort