Sorting Algorithms

Sorting Algorithms

Students will be able to...

• Describe the step-by-step process of selection and insertion sort algorithms

• Implement and modify sorting algorithms in Java

• Predict and trace the sorting process on sample datasets

• Compare the efficiency of algorithms using simulations and visualizations

• Reflect on how dataset size and order affect algorithm performance

Warm Up

Open Ended

If you had to organize books by height or name, how might you do it?

Warm Up

• Compare items and switch them around

• Use rules to decide which order is better

Open Ended

What are some ways computers could organize a list of numbers or names?

Warm Up

• Go one by one and put each in the right spot

• Find the shortest and move it to the start

Open Ended

Why might one method of sorting be better than another in some cases?

Warm Up

• If the list is already mostly sorted

• Some methods are faster with short lists

Insertion Sort vs. Selection Sort

• While loop will only run if the value directly before the unsorted value is less than the unsorted value

• The while loop won't execute for most of the unsorted values, lowering the execution count

Insertion Sort vs. Selection Sort

• Insertion Sort has to shift every single value when executing the while loop, as every value is less than the one before it

• Selection Sort will only swap 2 values- 4 and 0 then 3 and 1 before being completely sorted

Now It's Your Turn

• Head to CodeHS and access the Sorting Algorithms (Day 2) modules. You will be completing:

  • Insertion Sort Simulation

  • Exploration: Insertion Sort

  • Visualizing Sorting Algorithms, Pt 1

  • Visualizing Sorting Algorithms, Pt 2

  • Sorting Algorithm Reflection

Wrap Up

Match

Match the following concepts:

• Sorting algorithm that takes an array of values and sorts it. The idea is to have a sorted part of the list and an unsorted part. On each iteration, finds the lowest value in the unsorted section of the list and adds it to the end of the sorted part.

• Sorting algorithm that sorts an array of values. The idea is to have a sorted part of the list and an unsorted part. On each iteration of the algorithm, we grab the next unsorted element and place it in its proper position in the sorted section.

• The ability to achieve an end goal with little to no waste.

• A condition that holds true throughout a loop’s execution (e.g., part of the array is always sorted)

• A method for reordering data into a specific sequence

Selection Sort

Insertion Sort

Efficiency

Loop Invariant

Sorting Algorithm

• Selection Sort

• Insertion Sort

• Efficiency

• Loop Invariant

• Sorting Algorithm

Open Ended

What’s one difference between selection and insertion sort in how they treat the array?

Wrap Up

• Selection Sort- finds the smallest and swaps

• Insertion Sort- moves elements to insert each item in the correct position

Open Ended

What did you notice when sorting large datasets in the simulations?

Wrap Up

• Insertion Sort seemed faster when the data was almost sorted

• Both were slow on big random lists