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 ?