Differences

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

Link to this comparison view

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. ​
  • algorithms.txt
  • Last modified: 2019/03/31 14:49
  • (external edit)