CHAPTER 9: SORTING ALGORITHMS

9.1 BUBBLE SORT

9.1.1 How It Works

Compare adjacent elements
Swap if in wrong order
Repeat for entire list
Each pass places largest unsorted element at end
Continue until no swaps needed

9.1.2 Pseudocode

<PSEUDOCODE>

DECLARE myList : ARRAY[0:8] OF INTEGER
DECLARE UB : INTEGER
DECLARE LB : INTEGER
DECLARE index : INTEGER
DECLARE swap : BOOLEAN
DECLARE temp : INTEGER
DECLARE top : INTEGER

UB ← 8
LB ← 0
top ← UB

REPEAT
 swap ← FALSE
 FOR index ← LB TO top - 1
 IF myList[index] > myList[index + 1] THEN
 temp ← myList[index]
 myList[index] ← myList[index + 1]
 myList[index + 1] ← temp
 swap ← TRUE
 ENDIF
 NEXT index
 top ← top - 1
UNTIL NOT swap OR top = 0

9.1.3 Python Code

<PYTHON>

def bubbleSort(myList):
 n = len(myList)
 for i in range(n):
 swap = False
 for j in range(0, n-i-1):
 if myList[j] > myList[j+1]:
 myList[j], myList[j+1] = myList[j+1], myList[j]
 swap = True
 if not swap:
 break

myList = [70, 46, 43, 27, 57, 41, 45, 21, 14]
bubbleSort(myList)
print(myList)

9.1.4 Complexity

Best Case: O(n) - already sorted
Worst Case: O(n²) - reverse sorted
Space: O(1)

9.2 INSERTION SORT

9.2.1 How It Works

Assume first element is sorted
Take next element
Insert into correct position in sorted portion
Repeat until all elements sorted

9.2.2 Pseudocode

<PSEUDOCODE>

DECLARE myList : ARRAY[0:9] OF INTEGER
DECLARE UB : INTEGER
DECLARE LB : INTEGER
DECLARE index : INTEGER
DECLARE key : INTEGER
DECLARE place : INTEGER

UB ← 9
LB ← 0

FOR index ← LB + 1 TO UB
 key ← myList[index]
 place ← index - 1
 WHILE place >= LB AND myList[place] > key
 myList[place + 1] ← myList[place]
 place ← place - 1
 END WHILE
 myList[place + 1] ← key
NEXT index

9.2.3 Python Code

<PYTHON>

def insertionSort(arr):
 for i in range(1, len(arr)):
 key = arr[i]
 j = i - 1
 while j >= 0 and key < arr[j]:
 arr[j + 1] = arr[j]
 j -= 1
 arr[j + 1] = key

myList = [12, 11, 13, 5, 6]
insertionSort(myList)
print(myList)

9.2.4 Complexity

Best Case: O(n) - already sorted
Worst Case: O(n²) - reverse sorted
Space: O(1)