• Warm Up
• Explore Sorting Algorithms
• Practice
• Sorting Words
• Which algorithm is best?
• Hacks - Do an insertion sort with the new list (make actual code here)

Why Sort?

• Sort a list in ascending/descending order for binary search
• Sort into categories

Start with Numbers

Warm Up

• If the left number has a lesser value than that of the right number, then switch the numbers
• Find the least number then put as first element, then next least number than put as the next element, repeat in like sequence until all numbers sorted

example: [9, 62, 78, 54, 18, 74, 58, 84, 20, 46]

[9. 18, 20, 46, 54, 58, 62, 74, 78, 84]

Another (ineffective) method - randomize the list until the right order is achieved

Explore Sorting Algorithms

Notes on insertion sort:

• Array has sorted region, unsorted region
• Elements from unsorted region are put into positions in sorted region

Start by comparing first two elements and arranging in order –> create the sorted region (in a sub-array)

Then iterate by comparing the next element of the unsorted array with the largest element of the sorted array. If the unsorted element is largest, the unsorted element is at the end of the array. If not, the unsorted element is swapped below the largest element of the sorted array and compared with the next largest element of the sorted array until the newly-sorted element is in its proper position.

Merge Sort:

Split array into smaller arrays until you get 1 element list

Compare elements of smaller lists, merge them, sort them. Do this until you have one list.

Here’s what Lily said about combining the arrays once they have more than one element:

1. Compare the first index of the first array with the first index of the second array (note: these are guaranteed to be the least values of the array since they’re sorted arrays). The least value becomes the first index of the new subarray. Then, the next value of that array and the least value of the other subarray is compared, and iteration is employed…

Selection Sort:

Has sorted and unsorted arrays. Minimum value is placed at the first index for each pass, which becomes the sorted region. The next smallest value is switched to be put in the second index. Put the third smallest element in the third index. Do this until the list is sorted.

Practice

[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]

Selection Sort:

• 1st Pass: 0 is the least element. Swap 0 with the element of the 1st index, 75 - [0, 17, 46, 80, 67, 45, 69, 79, 40, 75]
• 2nd Pass: 17 is the next least element. It is already in the 2nd index.
• 3rd Pass: 40 is the next least element. Swap this with the 3rd index 46 - [0, 17, 40, 80, 67, 45, 69, 79, 46, 75]

etc

Bubble Sort:

• 1st Iteration: 17 is less than 75. Swap them - [17, 75, 46, 80, 67, 45, 69, 79, 40, 0]
• 2nd Iteration: 46 is less than 75. Swap them - [17, 46, 75, 80, 67, 45, 69, 79, 40, 0]
• 3rd Iteration: 80 is more than 75. Do nothing.
• 4th Iteration: 67 is less than 80. Swap them - [17, 46, 75, 67, 80, 45, 69, 79, 40, 0]

etc

[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]

Insertion Sort:

1. 88 is less than 39, swap them - [39, 88, 53, 39, 58, 43, 74, 81, 71, 51]
2. 53 is less than 88, swap them. 53 is greater than 39 - [39, 53, 88, 39, 58, 43, 74, 81, 71, 51]
3. 39 is less than 88, swap them. 39 is also less than 53, so swap again - [39, 39, 53, 88, 58, 43, 74, 81, 71, 51]

etc

Merge Sort:

1. Split the list into subarrays –> [88], [39], [53], [39], …
2. Merge subarrays [88] and [39] –> [39, 88]
3. Merge subarrays [53], [39] –> [39, 53]
4. Merge subarrays [58], [43] –> [43, 58]
5. [74, 81]
6. [51, 71]
7. Merge subarrays [39, 88] and [39, 53] –> [39, 39, 53, 88]
8. Merge subarrays [43, 58] and [74, 81] –> [43, 58, 74, 81]
9. Merge subarrays [39, 39, 53, 88] and [43, 58, 74, 81] –> [39, 39, 43, 53, 74, 81, 88]
10. Merge subarrays [51, 71] and [39, 39, …] –> [39, 39, 43, 51, 53, 71, 74, 81, 88]

Sorting Words

[‘taqua’, ‘radknight’, ‘gonococcal’, ‘unreproducible’, ‘blastogranitic’, ‘polyoecism’, ‘ulrichite’, ‘geosyncline’, ‘entomologist’, ‘kilnrib’]

Use selection sort –> [‘blastogranitic’, ‘entomologist’, ‘geosyncline’, ‘gonococcal’, ‘kilnrib’, ‘polyoecism’, ‘radknight’, ‘taqua’, ‘ulrichite’, ‘unreproducible’]

Which algorithm is best?

[0, 2, 6, 4, 8, 10] - insertion sort - swap 4 and 6 to complete the list! All other checks will result in no swaps.

[Elephant, Banana, Cat, Dog, Apple] - use selection sort. The check will swap Elephant and Apple; no other checks will result in swaps.

[29, 13, 83, 47, 32, 78, 100, 60, 65, 15, 24, 9, 40, 68, 53, 8, 90, 58, 39, 32, 34, 91, 74, 94, 49, 87, 34, 87, 23, 17, 27, 2, 38, 58, 84, 15, 9, 46, 74, 40, 44, 8, 55, 28, 81, 92, 81, 88, 53, 38, 19, 21, 9, 54, 21, 67, 3, 41, 3, 74, 13, 71, 70, 45, 5, 36, 80, 64, 97, 86, 73, 74, 94, 79, 49, 32, 20, 68, 64, 69, 1, 77, 31, 56, 100, 80, 48, 75, 85, 93, 67, 57, 26, 56, 43, 53, 59, 28, 67, 50] - use merge sort. This is a long list! Insertion sort and selection sort could be very long due to this. Split the list and merge the lists together.

Insertion sort, selection sort, and bubble sort has n^2 time complexity, whereas merge sort has nlog(n) time complexity.

Hacks - Do an insertion sort with the new list (make actual code here)

Using: Geeks for Geeks