Sorting, What is it? Why is it Important?

Whether it be a list of numbers that need to be sorted in order from largest to biggest, or a list of names to be organized alphabetically large database systems need to sort through lots of user input into an organized matter. Just as when organizing books in a library by subject, fiction non fiction, there are systems put in place to do so to the best efficiency, in order to get those books put away or sorted into their rightful place. Lets begin with naming different python sorting, lets use this list: 

[1,  34,  5,  6,  43,  2]
1) The Bubble Sort 

Bubble sort passes through the whole list, and switches items which are out of order, the first pass will result in the largest number being at the end of the list.

The list will look like this: 

[1,  5,  6,  34,  2,  43]

the runtime is O(n^2), the best case scenario everything is sorted, worst case everything will be exchanges 

2)Selection Sort 

Is an improvement of bubble sort as it only makes on exchange for each pass. Goes through the list, finds the largest integer and exchanges it with the last item 

in the list above after one pass the list will then be: 

[1, 34,  5,  6,  2,  43]

Selection sort makes just as many comparisons making it still O(n^2), however since there are less exchanges happening it usually will execute faster than bubble sort 

3) Insertion Sort 

It has a sublist that gradually gets larger and larger through each pass so, there will be a list of length one, where it is the smallest number. 

-Then there will be another item added from the original list, compared to figure where the next item should be located in the list, this continues until a final list that is sorted is returned. 

Still using O(n^2) 

4) Shell Sort 

Shell Sort is an improvement to insertion sort as it makes smaller sublists with an increment of i. Thos sublists are sorted through then after the increment decreases until reaching the increment of 1, Thus returning a fully sorted list. The runtime could fall between O(n) - O(n^2), it depends on the i. Which gives a little more control on how efficient the code could sort through a list of n size.

5) Merge Sort 

Significantly more efficient, it divides and conquers the list. Just as you might have to divide different tasks to a team of employees in order to get the job done the quickest.

It runs recursively, and continues to split the list in half until the base case of one item, then calls merge to sort through the two halves until the final list is returned. 

runs on O(nlogn) 

6) Quick Sort 

Takes the advantages of Merge sort without using the memory space, which could be in some cases an advantage, however could turn out not to work effectively in all cases. 

There is a pivot value usually the first item, who's main role is to split the list. This value is usually the split of the list. 

Then the left point and right point which are the items at the beginning of the list following the pivot value(if it is the first item), and the right being the the end of the list. 

The are then incremented(left) and decremented(right) until the left value is greater than the pivot, and the right is less then the pivot. Once these are found they are swapped this is repeated until the final list is sorted. In the best case, where the pivot point is chosen correctly, it will result in nlogn, however if there is uneven division, it could leave a runtime of O(n^2)