# Differences

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

algorithms [2019/01/12 03:48] paul [Sliding Window] |
algorithms [2019/03/31 14:49] (current) |
||
---|---|---|---|

Line 45: | Line 45: | ||

===== Sorting Algorithms ===== | ===== Sorting Algorithms ===== | ||

+ | |||

+ | Here's a breakdown of different sorting algorithms. There's sorting algorithms | ||

+ | that sort in place, rely on element comparisons, others that don't. | ||

+ | |||

+ | {{ ::sort_perf.png?direct&400 |}} | ||

+ | |||

+ | |||

==== Insertion Sort ==== | ==== Insertion Sort ==== | ||

Line 74: | Line 81: | ||

9. A[cur_smallest_index] = temp; | 9. A[cur_smallest_index] = temp; | ||

</code> | </code> | ||

- | ==== Divide and conquer ==== | + | |

+ | ==== Merge Sort ==== | ||

+ | | ||

+ | Merge sort is an O(n lg n) sorting algorithm that uses the dive and conquer | ||

+ | paradigm. | ||

+ | | ||

+ | {{ ::merge_sort.png?direct&400 |}} | ||

+ | | ||

+ | ==== Heap Sort ==== | ||

+ | | ||

+ | Heap sort is an O(n lg n) sorting algorithm that sorts in place with a constant | ||

+ | number of array elements stored outside the array at any time. | ||

+ | | ||

+ | Heapsort uses a data structure called a "heap" to manage information. | ||

+ | | ||

+ | {{ ::heapsort_heap.png?direct&400 |}} | ||

+ | | ||

+ | A heap is a binary-tree that consists of a root, and parent nodes that have up | ||

+ | to two child nodes. The math to retreive the the parent, left element or right | ||

+ | element of a node is really simple. | ||

+ | | ||

+ | **Parent** - $return\lfloor i/2 \rfloor$\\ | ||

+ | **Left** - $return 2*i$\\ | ||

+ | **Right** - $return 2*i+1$\\ | ||

+ | | ||

+ | There are two kinds of binary heaps, **max-heaps** and **min-heaps**. In both | ||

+ | kinds the values in the nodes satisfy a **heap property**. In **max-heap** the | ||

+ | **max-heap property** is that for every node $i$ other than the root, | ||

+ | | ||

+ | $A[Parent(i)]\geq A[i]$ | ||

+ | | ||

+ | For **min-heap** the **min-heap property** is that for every node $i$ other than | ||

+ | the root, | ||

+ | | ||

+ | $A[Parent(i)]\leq A[i]$ | ||

+ | | ||

+ | There are a set of operation algorithms that are used in conjuction with heaps. | ||

+ | They are as follows: | ||

+ | * Max-Heapify | ||

+ | * Build-Max-Heap | ||

+ | * Heapsort | ||

+ | * Max-Heap-Insert, Heap-Extract-Max, Heap-Increase-Key, Heap-Maximum | ||

+ | | ||

+ | === Max-Heapify === | ||

+ | | ||

+ | Runs in O(lg n), whose inputs are A and index i into the array. When it is | ||

+ | called, Max-Heapify assumes that the binary trees rooted at Left(i) and Right(i) | ||

+ | are max-heaps, but that A[i] might be smaller than its children. Max-Heapify | ||

+ | lets the A[i] value "float" down so that the subtree rooted at index i obeys the | ||

+ | max-heap property. | ||

+ | | ||

+ | - Is index left smaller than A.heap-size and A[l] > A[i]? | ||

+ | - If yes, largest = l | ||

+ | - Else, largest = i | ||

+ | - Is index right smaller than A.heap-size and A[r] > A[i]? | ||

+ | - If yes, largest = r | ||

+ | - Else, largest = i | ||

+ | - If largest != i | ||

+ | - exchange A[i] with A[largest] | ||

+ | - Max-Heapify(A, largest) | ||

+ | | ||

+ | === Max-Heap-Insert === | ||

+ | | ||

+ | Runs in $O(lg\ n)$ time. | ||

+ | {{ ::max-heap-insert.gif?direct&400 |}} | ||

+ | | ||

+ | <code> | ||

+ | Max-Heap Insert. Input: heap array A, with data from 1 to length, element to insert p | ||

+ | // stuff the element at the end of the heap array | ||

+ | 1. A[length+1] = p | ||

+ | // iterate up through the heap | ||

+ | 2. int i = length + 1; | ||

+ | 3. while i >= 0 | ||

+ | // check if the parent node of our inserted element is less than it. | ||

+ | 4. if (i/2 < p) | ||

+ | // swap the inserted element with its parent | ||

+ | 5. A[j] = A[j/2] | ||

+ | 6. A[j/2] = p | ||

+ | 7. j = j/2 | ||

+ | 8. else | ||

+ | 9. break | ||

+ | </code> | ||

+ | | ||

+ | === Build-Max-Heap === | ||

+ | | ||

+ | Build-Max-Heap uses Max-Heapify to a bottom-up manner to convert an array | ||

+ | A[1..n], where n = A.length, in a max-heap. This procedure goes through the | ||

+ | non-leaf nodes of the tree ($A[\lfloor n/2\rfloor..1]$) and runs Max-Heapify on | ||

+ | each one. | ||

+ | | ||

+ | <code> | ||

+ | Build-Max-Heap(A) | ||

+ | 1. A.heap-size = A.length | ||

+ | 2. for i = [A.length/2] down to 1 | ||

+ | 3. Max-Heapify(A,i) | ||

+ | </code> | ||

+ | | ||

+ | === Heapsort === | ||

+ | | ||

+ | Heapsort works by building a max heap and then deconstructing it in order which | ||

+ | in turn constructs a sorted array! Super neat and works in O(n lg n) time. | ||

+ | | ||

+ | The algorithm works as follows: | ||

+ | | ||

+ | <code> | ||

+ | Heapsort(A) | ||

+ | | ||

+ | 1. Build-Max-Heap(A) | ||

+ | 2. for i = A.length down to 2 | ||

+ | 3. Exchange A[1] with A[i] | ||

+ | 4. A.heap-length -- | ||

+ | 5. Max-Heapify(A) | ||

+ | </code> | ||

+ | | ||

+ | {{ ::heapsort.png?direct&600 |}} | ||

+ | | ||

+ | ==== Priority Queue ==== | ||

+ | | ||

+ | Apparently heapsort is great and all, but quicksort beats it. What people do use | ||

+ | is the heap data structure, with its most popular application being a priority | ||

+ | queue. A priority queue is a data structure that contains a set of keys sorted | ||

+ | by their priority. We use the following procedures when utilizing priority | ||

+ | queues. | ||

+ | | ||

+ | * Insert | ||

+ | * Find-Max | ||

+ | | ||

+ | There are others that you can implement, but will make it difficult to address a | ||

+ | element within the queue(([[https://www.youtube.com/watch?v=-WEku8ZnynU|Priority | ||

+ | Queues]])). | ||

+ | | ||

+ | * Delete-Max | ||

+ | * Change-Key | ||

+ | | ||

+ | ===== Divide and conquer ===== | ||

Many algorithms are recursive, they call themselves recursively to deal with closely related sub-problems. | Many algorithms are recursive, they call themselves recursively to deal with closely related sub-problems. |