CITS2200 - Lecture 4

← Back to Home

CITS2200 - Lecture 3
Insertion Sort & Intro to Complexity - Slides

Insertion Sort

• Insertion sort sorts elements in an array into non-decreasing order
  • Requires comparable elements in array (like binary sort)
  • Very simple, but also very inefficient sort method
• Insertion sort method:
  • Place two elements $a$ and $b$ such that they are sorted
  • If $a=b$ or $a<b$ → do nothing
  • If $a>b$, swap $a$ and $b$
  • This repeats along the array until the entirety is sorted
    Each element is compared with all elements along its left and is “inserted” into the correct place → hence insertion sort
• ! To insert an element into an array, we need to shift all the elements forward to “make room” → prevent overwriting data
  • Worst case → requires $O(n)$ time where $n$ is length of array
    We don’t care about this since it is a lower power than the overall complexity of the sort method. This is known as an asymptotic complexity as it has a less than proportional impact on cost.
  • See Insertion - Slides

def insertion_sort(A):
	for k in range(1, len(A)):
		cur = A[k]
		j = k
		
		while j > 0 and A[j-1] > cur:
			A[j] = A[j-1]
			j -= 1
		
		A[j] = cur
	
	return A

• This sort method has complexity of $O(n^2)$
  • This means that with array size $n$, it takes $n^2$ steps to sort
  • As we can see, insertion sort is very slow for large arrays

Complexity

$O$ is a constant used to represent operation cost in complexity

• It is known as big O notation

In the example above, $n^2$ represents the number of insertions, which we assume takes 1 unit of time to compute. But it actually takes more than that based on a number of varying factors Thus, we use $O$ to represent this varying operation cost.

In big O notation, we omit any constants that might be in front of $n$. We only care about the degree of the polynomial of $n$ as that is what affects the growth rate the most.

---

CITS2200 - Lecture 5