{{ message }}

Instantly share code, notes, and snippets.

# connoro7/sorting.md

Created Jul 16, 2020
An Intro to Sorting

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

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

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

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

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