Selection , quick and merge sorts.

• Selection Sort

Lets think about selection sort as two lists a sorted one and unsorted one. We will first start by comparing the first two numbers. In each step, find the smallest number in the unsorted part of the list, swap it with the first number in the sorted list until the whole list is sorted (n times). 

• Quick Sort

Quick sort is a recursive sorting algorithm in which we select an element in the list as a pivot and partition the list into two sublists around it ; one that contains values smaller than the pivot and one with values larger than the pivot. As we go we apply quick sort on our sublists.The performance of this algorithm depends entirely on selecting a good pivot. 

• Merge Sort

Instead of splitting the list into sublists around a pivot, merge sort splits the list into two halves , most likely equal, and recursively sorts them using merge sort. Finally, they are recombined by repeatedly take the smallest element among the two lists.

Sorting algorithms efficiencies

So I just had my tutorial today. It was pretty simple although recording the information in the spreadsheet took a lot of time but there are important points that we should benefit from :

• The List sort is the best in all cases (random, sorted and sorted reversed ) then comes the quick sort with both it's algorithms.
• When our data is sorted , bubble sort and insertion sort benefited the most from that.
• When our data is sorted reversed bubble sort was the most affected (i.e took more time ) since a swap will occur every time since numbers are in descending order and swapping takes time.

Deletion from binary search trees

We have three cases when deleting a node from a binary search tree:

• ·      If we are trying to delete a leaf , its simple we just remove it from the tree and the property of the BST is not violated.
• ·      If we are trying to delete a node that has one subtree, we connect its parent directly to its only subtree. In the following example we are trying to delete 3 and it has only one subtree:

•      The last case is when we have two subtrees; we follow this technique we leave the node that we want to delete and rather remove its value and search for another value that can be replaced their (without violating the BST property of course ) and then we delete the node that had the new value. For example:

       If we wish to delete the 6 in the following tree --------> we delete its value but keep       the actual node.

So the hint to finding the new value is one of two options its either the largest value in the left subtree or the smallest in the right subtree. Below is an illustration of how we replaced the value 3 and deleted the actual node.  

        

Binary Trees and Binary Search Trees

A tree is a data structure that consists of nodes and connections between them.
Properties:
* Each node has exactly one parent.
* There is a path from the root to every node.
* There are no paths in the tree that form loops .

Important terms:
Height of a tree : The length of the longest path between the root and a leaf.
Depth of a node : The length of the path from the root to the node.

A binary tree is a special kind of tree with a branching factor of 2. Lets apply what we learned in recursion to recursively define a binary tree:

A binary tree is :

• either empty or

• has a node with value k (root ) with a Binary Tree as its left child and a Binary Tree as its right child.

A binary search tree however is a special kind of binary tree with all nodes in our left subtree that have values less than the value k and all the nodes in our right subtree that have values more than the value k.

As shown above we can also define a binary search tree recursively simply by adding the property we just mentioned.

There are three important operations that we are concerned about it in binary search trees :

1. Searching for a certain value. 
2. Insertion.
3. Deletion.

Searching is relatively straight forward, where we compare the target's value to the root value and decide which subtree to recurse on.

Insertion however requires us to maintain the Binary Search Tree property after inserting the new value (i.e.insert the node where you would expect it to be if you did a binary search for its value).

Therefore insertion requires searching !!

Finally deletion,, uhmm deletion has a lot of cases and I would like to represent examples of these cases in another post to keep this post brief and clear.

With all these midterms going on and assignments here and there , thought you could have time for some computer science jokes. 

And a small advice maybe ?

Linked Lists and their efficiency

Aren't Python lists just based on arrays that consist of contiguous chunks of memory? But what if they didn't have to be contiguous ? What if we just want to add new elements into the memory without having to change the location of others ?

Now we can introduce a new data structure called Linked Lists which is simply a chain of connected nodes where each node contains a data field and a next field which points to the next node in the list. How do we reach to the end of the list ? We traverse the list by following each node's next pointer until we reach the end of our linked list. In most cases we have access to the first node which is called the head.

Adding and removing from Linked Lists
Adding a node replaces the last node reference to the new node that's being added and makes our old last node point to the new node as the next node in the list.
Deleting a node is a process that iterates the list looking for the node and and we look around the deleted node to make sure that the previous node now points to the following node as its next node.

Linked list efficiency:
Most operations that we apply to either end of our linked list do not depend on the size of the list but only one operation does which is removing from the end of the list .
Why ?!
Because removing from the end of the list requires a full traversal since we can't obtain our new tail just from tail.

Difference between abstraction and encapsulation

After introducing the concept of Object Oriented Programming and its main parts, lets compare and contrast abstraction and encapsulation :

Abstraction :

• Solves our problem using an outer shell in terms of  "design"
• Its used to hide the unwanted and un relevant data from the user.
• Focuses more on what the object actually does rather on how it does it.
• Example : The display of a touch screen.

Encapsulation:

• Solves our problem in the implementation level instead.
• It is used to hide the code and data into one single unit and hide it from the external world.
• Focuses on hiding the internal details and mechanics of an object, i.e. how the object does it.
• Example : How the display screen is connected with dialling option using circuits.