Sorting and Efficiency

Sorting is essentially a way of taking a list of unordered elements and ordering them in a specific way, e.g. smallest-to-greatest or greatest-to-smallest. However, there is one key difference between sorting items via programming and sorting items requires an algorithm. An algorithm is a set of instructions that will test elements and put them in a certain place according to a rule.There are multiple ways of doing this, each with pros and cons. In this post, I will primarily discuss three types of sorting: bubble sort, selection sort, and insertion sort.

Bubble sort employs an algorithm that goes through every index in a list, and checks if the item at that index is greater than the item succeeding it. If it is, it swaps the item, this process continues until the function reaches the second last index, at which point the list is sorted. The diagram below illustrates the method of sorting.

Taken from http://mytutorialspace.com/bubble-sort/

Selection sort. The first pass of this sorting algorithm takes the smallest item in the list and places it at index 0, i.e. at the start of the list, thus creating a sorted and sorted side of the list.After the first pass, the sorted section is comprised only of the item at index 0; this is the only item that we know for certain is sorted. The next pass will take the smallest item in the unsorted section and move it to index 0 of the unsorted section, i.e. one index after the end of the sorted section. In this way, the sorted section will be comprised of two sorted numbers in the next pass. The size of the sorted section will increase by one, and the unsorted section will decrease by one. This process continues until the length of the unsorted section equals one. This means that the item in the unsorted section is the largest number. Hence, the list is sorted. The diagram below clearly illustrates this concept.

Red: sorted, Blue: unsorted
Taken from http://mytutorialspace.com/write-program-demonstrate-selection-sort-array/

Insertion sort. This algorithm starts by taking the first two indexes, 0 and 1, and comparing their sizes. It will swap them if index 0 is larger than index 1. Otherwise, it will do nothing. After this occurs, index 0 and 1 can be considered a sorted region. The rest, for all we know, are unsorted. The algorithm then moves forward one index at a time and checks if the item at that index is less than any of the items in the sorted region. If it is less, the sorting algorithm will move that item behind the item that it is closest to it in size, but still greater than it. Otherwise, the algorithm will proceed to the next index. This continues until the end of the list. The diagram below show this concept.

Red: sorted, Blue: unsorted
Taken from http://www.stoimen.com/blog/2012/02/13/computer-algorithms-insertion-sort/

Efficiency. Each of these algorithms have different time complexities, they require different amounts of time to output the desired result.

To measure these time complexities, the standard is to use Big-Oh. O(n) means the sorting algorithm indexes every item in the list, where n represents the amount of items. O(1) means that the sorting algorithm's time complexity. It is invariable, so we represent it using a constant value, i.e. 1.