Skip to content

Instantly share code, notes, and snippets.

@connoro7
Created Jul 16, 2020
Embed
What would you like to do?
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.

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.


sort



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.



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.

sort



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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment