Opening discussion (small groups - same as last time!) :

Create a Notion page like we did on Friday, and consider the situation below.

Imagine you have a pile of an unknown number of cards (like poker cards), and you need to sort them (smallest to largest). Assume they are all of the same suit. How would you do it?

Things to consider (which approach would you take?)

• You can see all of their values at once
• You draw one card at a time
• You start sort from the smallest value (Ace)
• You start sorting from the largest value (King)

Write down each step in clear, precise instructions, such that someone else reading it is clear on what you would do. Then show it to someone else in your group and see if they can describe it.

After this is done, move on to the Insertion Sort discussions...

Jack: Place the first card.

order from least to greatest

for every pair picked (assuming the first one is the left and the second one is the right),

if the left is larger than right, switch

5 3 4 1

3 5 4 1

3 4 5 1

3 4 1 5

Look at the code below for Insertion Sort, written in pseudocode (note that the textbook's format may be a bit different), and see if you can figure out what it's doing (individually)

• [x] Write down the first series of swaps (when i = 1) individually, then wait for everybody else in your group to finish. Compare your arrays.
• [x] Continue together for the rest of the array (you can skip writing the changes for the while loop, but make sure to write a separate array for each for-loop change (i.e., every time i changes)

<aside> 💡 [ 24 | 21 | 55 | 8 | 76 | 6 | 2 | 66 | 50 | 82 ] ****

</aside>

Algorithm InsertionSort(dataList)
// dataList is a zero-indexed list/array of sortable data
// n is the length of dataList
// algorithm modifies the dataList; returns the modified list
for i = 1 to n-1 do
	let j = i
	while j > 0 and dataList[j] < dataList[j-1] do
		swap dataList[j] and dataList[j-1]
		let j = j - 1
return dataList

<aside> 💡 [ 24 | 21 | 55 | 8 | 76 | 6 | 2 | 66 | 50 | 82 ] ****

</aside>

Algorithm InsertionSort(dataList)
// dataList is a zero-indexed list/array of sortable data
// n is the length of dataList
// algorithm modifies the dataList; returns the modified list
for i = 1 to n-1 do
	let j = i
	while j > 0 and dataList[j] < dataList[j-1] do
		swap dataList[j] and dataList[j-1]
		let j = j - 1
return dataList

21 24 55 8 76 6 2 66 50 82 // do 21

21 24 55 8 76 6 2 66 50 82 // do 24

21 24 55 8 76 6 2 66 50 82 // do 55

8 21 24 55 76 6 2 66 50 82 // do 8

8 21 24 55 76 6 2 66 50 82 // do 76

6 8 21 24 55 76 2 66 50 82 // do 6

2 6 8 21 24 55 76 66 50 82 // do 2

2 6 8 21 24 55 66 76 50 82 // do 66

2 6 8 21 24 50 55 66 76 82 // do 50

2 6 8 21 24 50 55 66 76 82 // do 82