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