Sorting and Efficiency

Everyone knows that when you are looking for something, it's easier when the place where you're looking is neat. The same applies to computer science. When you are looking for a number in a large list of numbers, an easy way to do so is to first sort the list.
There are different methods of sorting in python:


1. BubbleSort
In BubbleSort, we compare adjacent pair of numbers by first taking the first and second numbers from the left. If the number on the left is greater than the one on the right, swap it. Then, take the second and third numbers, again comparing them and swapping if the number on the left is greater than the number of the right. Continue this process until the largest number is to the far right. This is know as the first pass. After the first pass, we are now working with n-1 items in the list. So we start the process with the second number in the list from the left. Continue each pass until the list is sorted.
Here is an example on a small list:
L = [1, 0, 4, 2, 3]

First pass:
Step 1 - 1 > 0, therefore swap. L = [0, 1, 4, 2, 3]
Step 2 - 1 < 4, therefore no change. L = [0, 1, 4, 3, 2]
Step 3 - 4 > 3, therefore swap. L = [0, 1, 3, 4, 2]
Step 4 - 4 > 2, therefore swap. L = [0, 1, 3, 2, 4]

Second pass:
Step 1 - 1 < 3, therefore no change.
Step 2 - 3 > 2, therefore swap. L = [0, 1, 2, 3, 4]
Step 3 - 3 < 4, therefore no change.

List is now sorted. This method is probably the most inefficient as it must exchange items until the last location is known.
Therefore the time complexity of the BubbleSort would be at most O(n^2)


2. SelectionSort
The SelectionSort is an improvement of the BubbleSort. Like it name indicates, it uses a selection method. During the first pass, it looks for the largest number and swap it with the n-item in the list.
During the second, it now looks for the second largest number and swap it with the n-1 item in the list.
Here is an example on a small list:
L = [43, 50, 47, 24, 12]

First pass:
50 is the largest, swap it with 12. L = [43, 12, 47, 24, 50]

Second pass:
47 is the largest, swap it with 24. L = [43, 12, 24, 47, 50]

Third pass:
43 is the largest, swap it with 24. L = [24, 12, 43, 47, 50]

Fourth pass:
24 is the largest, swap it with 12. L = [12, 24, 43, 47, 50]

List is now sorted. Since it makes pretty much the same number of comparisons as the BubbleSort, the time complexity of the SelectionSort is also, at most, O(n^2)


3. InsertionSort
This method is different from the previous two mentioned above. It works by always keeping a sorted sublist in the left side of the list. Whenever a number is larger than the one after it, it is inserted in the sorted sublist. If the number on the right is greater than the number on the left, it is only added to the right of the number on the left, in the sublist.
Here is an example on a small list:
L = [53, 26, 80, 70, 51]

First pass:
53 is the first number in the sorted sublist.
53 > 26, therefore insertion. L = [26, 53, 80, 70, 51]

Second pass:
53 and 26 are in the sorted sublist.
53 < 80, therefore 80 is only inserted in the sorted sublist, to the far right. L = [26, 53, 80, 70, 51]

Third pass:
53, 26 and 80 are in the sorted sublist.
70 < 80, therefore insertion. L = [26, 53, 70, 80, 51]

Fourth pass:
53, 26, 80 and 70 are in the sorted sublist.
51 < 80, therefore insertion. L = [26, 51, 53, 70, 80]

Note that the sublist is always sorted.  It begins with only the first number of the main list in it, and goes on until all the numbers from the main list are in the sublist.
Its time complexity is also O(n^2) at most.


4. ShellSort
The ShellSort is an improvement of the InsertionSort. It works by breaking the main list into smaller sublists, where each one of them are sorted using the InsertionSort method.
Here is an example.
Let L = [54, 26, 93, 17, 77, 31, 44, 55, 20]
We break L into three sublists:
L1 = [54, 17, 44]
L2 = [26, 77, 55]
L3 = [93, 31, 20]

Next, we sort each sublist.
L1_sorted = [17, 44, 54]
L2_sorted = [26, 77, 55]
L3_sorted = [20, 31, 93]

Once every sublists have been sorted, increment them together to form the main list, now sorted.
Being an improvement of the InsertionSort method, the time complexity of the ShellSort is at most between O(n) and O(n^2).


5. MergeSort
This method uses a divide and conquer strategy. Unlike the first four methods, the MergeSort is a recursive algorithm that continually divides a list in half. A list is then sorted if and only if it is empty or has only one item. We then use the operation called merging. Merging is the process of taking two smaller lists and combining them together to form a single, sorted list.
Here is an example:
Let L = [54, 26, 93, 17, 77, 31, 44, 55, 20]

Using the MergeSort, the list has been splitted into smaller lists.
We now use the merge operation to merge the smaller lists into one single list.

A MergeSort is a O(n log n) algorithm.