CST-370 Week 5

 This week, I learned to apply the "Divide-and-conquer" technique in a sorting algorithm, known as "Quick-sort." I also learned about "Decrease-and-conquer", which is a similar technique to divide-and-conquer and is used in sorting algorithms, such as "Insertion sort" and Khan's algorithm. A third technique I learned is the "Transform-and-Conquer" technique, which is used in "Pre-sorting."

I also began to understand the efficiency of the algorithms used for Binary Tree traversal and height calculation.

Quicksort

Uses the Divide-and-conquer technique. It is "in place", like insertion sort, but not like merge sort (does not take up extra space)

Quicksort of an n-element array:

1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray < x < elements in upper subarray

2. Conquer: Recursively sort the two subarrays.

3. Combine

Example of Partitioning

Worst case: O(n^2) <- theta

Best case O(nlogn) <- theta

Binary Tree Traversal

A binary tree is a divide-and-conquer ready data structure.

3 binary tree traversals: In-order, pre-order, and post-order

Examples:

Binary Tree Height

Defined as: The length of the longest path from the root to the leaf node in the tree. Can indicate the worst-case scenario for searching. Height of empty tree = -1. Height of binary tree with one node = 0

How to calculate: Calculate the height of the left subtree and right subtree and then take the max. The height of the binary tree is one longer than the maximum height of T_l and T_r