Sorting and efficiency

Sorting is a procedure of organizing elements in a certain order. There are have been developed many sorting algorithms, but the most used ones are insertion, bubble, selection, shell, merge and quick sorts. 
1) Bubble Sort - Big O(n^2):
The Bubble Sort makes multiple passes through a list, comparing two adjacent items and swapping them if they are out of order. For example bubble sort on ( 9 1 4 3 10 ):
First Pass:
( 9 1 4 3 10 )  ( 1 9 4 3 10 ), The algorithm compares the first two items and swaps them  since 9 > 1.
( 1 9 4 3 10 )  ( 1 4 9 3 10 ), Swap since 9 > 4
( 1 4 9 3 10 )  ( 1 4 3 9 10 ), Swap since 9 > 3
( 1 4 3 9 10 )  ( 1 4 2 9 10 ), Since the 10 > 9 the algorithm doesn't swap the numbers.
After multiple passes of bubble sort the list will be completely sorted.

2) Selection Sort - Big O(n^2):
The Selection Sort finds the biggest number in the list and puts it to the proper location.
Example: bubble sort on ( 9 1 4 3 10 ):
( 9 1 4 3 10 ) -> ( 9 1 4 3 10 ) Since 10 is the largest item in the list, the algorithm is not going to change anything.
( 9 1 4 3 10 ) -> ( 3 1 4 9 10 ) Since 9 is the second greatest item in the list, the algorithm swaps 9 with 3.
And so on till the list is sorted.

3) Insertion Sort - Big O(n^2):
The algorithm always keeps a part of the list sorted and adds up items to the sorted part of the list as it progresses. Example: ( 9 1 4 3 10 )
( 9 1 4 3 10 ) -> ( 1 9 4 3 10 ) Swaps 9 and 1 because 9 > 1
( 1 9 4 3 10 ) -> ( 1 4 9 3 10 ) Inserts 4 between 1 and 0.
( 1 4 9 3 10 ) -> ( 1 3 4 9 10 ) Inserts 3 to the proper location.
( 1 3 4 9 10 ) -> ( 1 3 4 9 10 ) The list is fully sorted.

4) Shell Sort - Big O(n^2):
The Shell Sort improves Insertion Sort by splitting the list into multiple parts and sorting them with Insertion Sort. The algorithm uses an increment i as a gap between the numbers. After every pass the algorithm reduces the increment.
Example: sorting ( 9 1 4 3 7 8 2 5 6) with i = 3
( 9 1 4 3 7 8 2 6 5) The highlighted items are the first numbers of the sublists.
Doing the insertion sort through the sublists we get:
( 1 4 9 3 7 8 2 5 6) setting i = 2
( 1 4 3 9 7 8 2 5 6 ) After this the algorithm does the standard Insertion Sort.
( 1 2 3 4 5 6 7 8 9 )

5) Merge Sort - Big O(logn):
It is a recursive algorithm that splits the list in half till every sublist consists of 1 item. Then, the algorithm merges 2 adjacent sublists and sorts them again. Example: 
1) ( 9 1 4 3 10 )
-> 9, 1, 4 , 3, 10 -> (1, 9), (3, 4) (10) -> (1, 3, 4, 9) (10)
2) 

Linked Lists

Week 8 was about linked structures.  They were confusing at first, but lectures and the lab made me understand Linked Lists better. A Linked List is a recursive data structure that consists of groups of nodes. Every node is consisted of data (head) and reference (rest) to the next node:

Recursion

Although it seems a bit complicated at first, Recursion is one of the most useful methods in computer science. It took me a while to understand Recursion, but at the end it's worth it. Doing the Assignment 1 helped me a lot in understanding it.  Basically, Recursion is running the same function over and over again till a condition is met. There's a example of recursion(finding the nested depth of a list):

def nested_depth(L):
    return (1 + max([nested_depth(x) for x in L] + [0]) if isinstance(L, list) else 0)

So what this function does is, it loops over all of the elements of list L and adds 1 every time the element is list, if the element is not list it adds 0.

Overall Recursion is a great method that makes hard tasks easier to solve and save tens of lines of code.

Assignment 1 and Recursive Structures

This week I started the first assignment. Which seemed easy till I got to the 5th step. The assignment is about Towers Of Hanoi. It took me a long time to figure out the recursive algorithm for the 5th step, but I did it eventually. Recursion itself didn't make sense to me at first, but after the last weeks lab it started getting clearer.

SLOG 1: Object Oriented Programming (OOP)

        Today I'm going to talk about Object Oriented Programming (OOP). Unlike Procedural Programming, the paradigm that has been used widely till 1980s, OOP focuses on the creation of objects that contain both data and functionality. Objects, the instances of classes, are used with other objects to build up programs. Objects interact with each other using methods. Some of the most popular examples of OOP languages are: Python, C++, Java, PHP.
       One of the main characteristic of OOP is that, it emphasizes on data rather than procedures. The paradigm puts sets of methods into classes, making them easier to use and implement into other classes.  Another upside of class-based programming is that, it provides brevity. A program including hundreds of lines can be broken down to pieces, which makes it more organized and thus easier to understand. Overall, OOP provides more flexibility, comprehensibility and concision.


Recursion

     Means defining something by itself, usually multiple times. It's used for calling the same function over and over again until the goal is achieved. The main upside of recursion is that, it allows us to code the program more efficiently. We can cut down 100 lines of program to less than 10 using recursion.