#### Transcript EE113D Project: Heap Sort - University of California, Los

EE113D Project: Heap Sort Shuofei Geng Michael Utanes Felix Lu Heap Sort - Motivation Concept of Sorting present in everyday life: Sorting a list of grades MP3 Files on a computer Names on a phone Directory More advanced engineering problems rely on efficient sorting problems Heap Sort one of the best general-purpose sorting algorithms Applications: Priority Queues, Interval Scheduling Heap Sort – Project Goals Implement the Max Heap Sort Algorithm Utilize existing C code and convert to assembly language for use on using the DSK Plus Board Input data a random array of integer values Output data an array sorted in ascending order 5 3 1 2 4 1 2 3 4 5 What is Heap Sort? Sorting Algorithm that first places objects into a heap Heap organized such that the largest value can easily be extracted while preserving heap structure Each time we delete (extract) the maximum, we place at next open position from the end of the sorted array Keep extracting largest value of heap until none remains, giving the elements in order Heap of remaining unsorted elements Sorted elements The Heap Heap can be represented as a balanced binary tree Each element is stored at a node. Max-Value at root of tree 16 Heap Order: A Parent node can 15 13 have two Child Nodes The value of the Parent node always 14 12 10 11 larger than the Child Nodes 8 5 3 4 6 2 1 Heap Sort – SiftDown Operation The siftDown() function is used to build and reconstruct the heap function sift(a, start, count) { var int root := start, child while root * 2 + 1 < count { //compare with two children, make swap child := root * 2 + 1 //if chlidren larger than value; if not keep traversing if child < count - 1 and a[child] < a[child + 1] child := child + 1 if a[root] < a[child] swap(a[root], a[child]) root := child else return } 16 //Organize Heap //node in position i is parent of the nodes in positions 2*i and (2*i+1) } 15 13 14 12 10 11 8 5 3 4 6 2 1 Heap Sort : Pseudocode function heapSort(a, count) { var int start := count ÷ 2 - 1, end := count - 1 while start ≥ 0 sift(a, start, count) start := start - 1 while end > 0 swap(a[end], a[0]) sift(a, 0, end) end := end - 1 //Build Heap //Root Deletion //Heap Reorganized } function sift(a, start, count) { var int root := start, child while root * 2 + 1 < count { //compare with two children, make swap child := root * 2 + 1 //if chlidren larger than value; if not keep traversing if child < count - 1 and a[child] < a[child + 1] child := child + 1 if a[root] < a[child] swap(a[root], a[child]) root := child else return } //Organize Heap //node in position i is parent of the nodes in positions 2*i and (2*i + 1) } Heap Sort : Pseudocode Heap Sort Comparison with Other Sorts Merge Sort & Quick Sort Splits the items to be sorted into two groups, recursively sorts each group, and combines them into a final, sorted sequence Generally faster than heap sort, due to better data cache performance Comparison with Other Sorts Runtime (Worst Case) Extra Space Required Stable? Heapsort O(n*logn) None No Mergesort O(n*logn) O(logn) Yes Quicksort O(n^2) O(logn) No Applications of Heap Sort Interval Scheduling List of tasks with various start/finish times Aim to perform tasks within specified time interval without overlapping Sort finish time of tasks then take earliest finish time until all tasks performed Priority Queue - Supports the following three operations: Add an element to the queue with an associated priority Remove the element from the queue that has highest priority, and return it Peek at the element with highest priority without removing it Ex. Bandwidth Management Heap Sort Implementation Project Development First decide on topic for implementation Then Model Sorting algorithm with High Level Language (C or matlab) Challenge: No previous Heap Sort project exists “Write Everything From Scratch” Internet contains many topics/code on Heap Sort Lastly, Program/Debug Max Heap Sorting Algorithm Utilize existing C code and convert to assembly language for use on using the DSK Plus Board Program consists of 2 files: randomno.asm, heapsort.asm Heap Sort Implementation Program consists of two files: randomno.asm - # list, containing 100 random #’s To create list, we wrote a short C program “RandomNoGenerator.c” that outputs random #’s in assembly format i.e. “.word 4” Then we copied the input data to the correct file type to represent random array heapsort.asm – Executable code Implements heap sort algorithm Heap Sort Implementation heapsort.asm Design Challenges: Use of Pointers Comparison Operations Flags TC & NTC Function Usage When to use “#” & “*” Limited amount of Registers (AR0-AR7) Implementation Passing Parameters Returning from Function Adding “nop” instruction Heap Sort Implementation heapsort.asm Debugging Challenge: Adding “nop” Instruction While executing program in whole program misbehaves Due to certain instructions taking longer than a cycle to complete, thus not properly registering values in time Solution: Add “nop” instruction between lines where this is true Found by use of Breakpoints in code Heap Sort – Discussion of Results Program correct in implementing Heap Sort Output a sorted array Also Concerned about Program Efficiency Does it meet the time requirement O(n*log2(n)), where n is the # of elements in the array? Heap Sort – Discussion of Results Does it meet the time requirement O(n*log2(n))? 1st- Check # of times siftdown2() is called 2nd- See # iterations performed inside function After function returns, the 1st and last element of array is swapped Process stops until function calls Max ‘n’ times After every iteration, multiply the current index by 2 then use as current index Since only checking index which is in power of 2 of the original root passed in as parameter, we can do at most log2(n) operations Therefore O(n*log2(n)) is satisfied Heap Sort - Summary Positives: Does not require multiple arrays Does not include recursion Optimal for large data sets Runs well with computers with slow data caches Negatives: Generally Slower than Merge Sort/Quick Sort Unstable