connoro7/sorting.md

## sorting.md

      
    Raw
  

              sorting.md
            
          
    Introduction to Sorting


Objectives


Implement a bubble sort algorithm
Implement a selection sort algorithm
Implement an insertion sort algorithm


Sorting Efficiency

There are many ways to sort data, some faster than others. Consider for example this horribly slow sorting algorithm, called Bogosort:

Randomly shuffle the list.
Check if it is sorted.

If the list is not sorted, repeat steps 1 and 2.
If the list is sorted return the sorted list.


Volunteer Algorithm


Bubble Sort


For each element in the list:

For each element in the list, look at the element to the right.
If the value on the left is greater than the value on the right, swap the two values.
Keep swapping until you're at the end of the array. Then move onto the next element in the array and repeat.


With each iteration, the smaller element in the list bubbles up towards the beginning of the array.


Visualgo
Bubble Sort Animations


Can be implemented using multiple loops (at least two) or recursion.


Complexity Analysis


n - 1 comparisons done in 1st pass
n - 2 in 2nd pass
n-3 in 3rd pass etc.

(n-1)+(n-2)+(n-3)+.....+3+2+1
Sum = n(n-1)/2


O(n^2)


Bubble sort is NOT an efficient algorithm


OK for small number of elements
Great intro to sorting


Bubble Sort with Hungarian ("Csángó") folk dance

<iframe width="560" height="315" src="https://www.youtube.com/embed/lyZQPjUT5B4" frameborder="0" allowfullscreen></iframe>

Volunteer Bubble Sort


Selection Sort


Assume the first item is the smallest value (minimum).
Compare this item to the second item.
If the second item is smaller than the first, set the second item as the new minimum.
Continue until you reach the end of the array.
If the minimum value (index) is not the item (index) you started with, swap them.


Similar to Bubble Sort, but instead of comparing each array item to its neighbor, the goal is to locate the smallest remaining value and drop it into the correct place in the array.


Visualgo
Selection Sort Animations


Complexity Analysis

O(n^2)

Selection sort does not adapt to the data in any way (notice that the four animations above run in lock step), so its runtime is always quadratic.
However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

Selection Sort with Gypsy folk dance

<iframe width="560" height="315" src="https://www.youtube.com/embed/Ns4TPTC8whw" frameborder="0" allowfullscreen></iframe>

Volunteer Selection Sort


Insertion Sort


An insertion sort works by separating an array into two sections:

a sorted section
an unsorted section.

Initially, the entire array is unsorted.


If the item value goes after the last item in the sorted section, then do nothing.
If the item value goes before the last item in the sorted section, remove the item value from the array and shift the last sorted item into the now-vacant spot.
Compare the item value to the previous value (second to last) in the sorted section.
If the item value goes after the previous value and before the last value, then place the item into the open spot between them, otherwise, continue this process until the start of the array is reached.


Visualgo
Insertion Sort Animations


Complexity Analysis

O(n^2)

Although it is one of the elementary sorting algorithms with O(n^2) worst-case time, use insertion sort when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

Insertion Sort with Romanian folk dance

<iframe width="560" height="315" src="https://www.youtube.com/embed/ROalU379l3U" frameborder="0" allowfullscreen></iframe>

Volunteer Insertion Sort


Objectives


Implement a bubble sort algorithm
Implement a selection sort algorithm
Implement an insertion sort algorithm