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)  

Week 7: Recursion, how we love thee.

Week 7: recursion 

Recursion is hard to completely understand mainly because when programming recursively, you need to understand exactly what your program needs to originally do then call it within itself. Also you need to ensure your program won’t run an infinite amount of times, making the depth of recursion to large, and it not working at all. 

How I have been programing before took special cases in if statements however in recursion, one way to adapt from previous knowledge is by using the idea of these ‘special cases in if statements or possibly in while loops, but making them into a base case from your initial function then calling those base cases recursively in regards to your arguments. 

This is best explained by an example: 

the Fibonacci sequence of numbers can be expressed recursively as so: 

def fib(n: num)-> int: 

if n == 1: 

return 0          (THESE ARE YOUR BASE CASES) 

if n == 2: 

return 1 

# now you have two initial numbers and for all other cases you will want to get the fib sequence for n minus your base case values for n 

return fib(n - 2) + fib(n - 1) 

looking at this code you may wonder how does this work?

fib(3) 

will process it from the return statement then call then call what the values of 

fib(3 - 2) + fib(3 - 1) 

fib(1) + fib(2) 

0 + 1 

1 will be returned 

now fib(3) == 1 

say you want to call fib(4) 

fib(4-2) + fib(4-1) 

fib(2) + fib(3)  ------> (fib 3 is then called recursively giving the second value of 1)

1 + 1 

the return int will be 2 

say you want to call fib(5) 

fib(5 - 2) + fib(5 - 1)   

fib(3) + fib(4)   ------>   (value fib(3) and fib(4) are already within your program)

1 + 2 

the return int will be 3 

and so on, recursive works well as the function is actually recursively keeping track of each value needed instead of you programing the fib sequence and giving it the value. Essentially being the best approach to program the Fibonacci sequence 

This is a simple example, however once having an idea of approaching it as: 

1. make a base case of what you want to be accomplished with your program
2. then if a special case is called you will call the function once again