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

Our group’s ideas:

• ArrayList if the exact cards are known
• For an entire deck of cards, first sorting by number and then by suit
• For an entire deck of cards, first sorting by suit and then by number
• If the number of cards and type of cards are unknown, then PriorityQueue, BinarySearchTree, or insertion sort
• Start with resuming Insertion Sort discussions.

  • [x] 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)

    Sorts the array from least to greatest

  • [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