Bootcamp

Search…

📅

Course Schedule

🛠

Course Logistics

🏞

Projects

0: Language and Tooling

1: Frontend Basics

🌈

CSS

2: Backend Basics

3: Backend Applications

4: Backend Structure

5: Full-Stack Applications

6: Frontend Infrastructure

7: React

8: Advanced React

9: Advanced Topics

🧮

Algorithms

💼

Interview Prep

☺

User Experience

0: Language and Tooling Teaching Guide

1: Frontend Basics Teaching Guide

🌈

CSS Teaching Guide

2: Backend Basics Teaching Guide

3: Backend Applications Teaching Guide

4: Backend Structure Teaching Guide

5: Full-Stack Applications Teaching Guide

6: Frontend Infrastructure Teaching Guide

7: React Teaching Guide

8: Advanced React Teaching Guide

9: Advanced Topics Teaching Guide

🧮

Algorithms Teaching Guide

💼

Interview Prep Teaching Guide

☺

User Experience Teaching Guide

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 AlgorithmsSelection 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

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

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.

Further Reading

Last modified 2mo ago