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.

Steps to sorting the cards:

1. Draw the first
2. compare it to the rest of the card
3. swap positions, if it is smaller than the current card

[ 5, 2, 6, 4,1 ]

1. Compare 5 to 2: 5 > 2, swap [2, 5, 6, 4, 1]
2. Compare 5 to 6: 5 < 6, move on [2, 5, 6, 4, 1]
3. Compare 5 to 4: 5 > 4, swap [2, 4, 5, 6, 1]
4. Compare 5 to 1: 5 > 1, swap [2, 4, 1, 5, 6]

Another method:

1. Compare 2 to 5: 2<5, same [2, 5, 6, 4, 1]
2. Compare 2 to 6: 2<6. same [2, 5, 6, 4, 1]
3. Compare 2 to 4: 2<4, same [2, 5, 6, 4, 1]
4. Compare 2 to 1: 2>1, bigger [1, 2, 5, 6, 4]
5. Compare 5 to 6: 5<6, same [1, 2, 5, 6, 4]
6. Compare 5 to 4: 5>4, bigger [1, 2, 4, 5, 6]

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

• [ ] 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)
• [ ] Write down the first series of swaps (when i = 1) individually, then wait for everybody else in your group to finish. Compare your arrays.
• [ ] 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

1. i =1, j = i,

   j> 0 ; true

   dataList[j] < dataList[j-1] (21 < 24) ; true

   [ 21 | 24 | 55 | 8 | 76 | 6 | 2 | 66 | 50 | 82 ] ****

   j = 0

   j !> 0 , while loop terminates

2. i = 2, j = i

   j>0, true

   dataList[j] < dataList[j-1] (55 > 24); not true

[ 21 | 24 | 55 | 8 | 76 | 6 | 2 | 66 | 50 | 82 ]

1. i = 3, j = i

   j > 0, true

   dataList[j] < dataList[j-1] (8 < 55); true

   [ 21 | 24 | 8 | 55 | 76 | 6 | 2 | 66 | 50 | 82 ]

   j = j -1 = 2

   8 < 24 true

   [ 21 | 8 | 24 | 55 | 76 | 6 | 2 | 66 | 50 | 82 ]

   j = 1

   8 < 21 true

   [ 8 | 21 | 24 | 55 | 76 | 6 | 2 | 66 | 50 | 82 ]