1. Implement in the language of your choice a function or method which takes in
ID: 3572718 • Letter: 1
Question
1. Implement in the language of your choice a function or method which takes in a vector or list of integers and sorts the list using the heap sort algorithm. You can either modify the list given (past by reference) or produce a new sorted list (pass by value). The worst case run time for this function must be O(nlog(n)).
2. Implement a function or method in the language of your choice which takes in a vector or list of integers and sorts the list using the quicksort algorithm. Your function must either modify the given list, or return a new sorted list. The average run time for this function must be O(nlog(n)). The worst case run time can be O(n).
3. Implement a function or method in the language of your choice which takes in a vector or list of integers and also takes in another integer d which we will refer to as depth. The function will recursively call quicksort similar to problem 2 while decrementing depth until the depth has reached 0. At which point the algorithm will switch over to the heapsort you implemented in problem 1 to nish the sorting of the vector. For this problem also comment in the code what the value of d needs to with respect to the size of the vector n for the algorithm to have worst case run time of O(nlog(n)).
4. You should have the above 3 problems implemented as functions. You also should have an implementation of a heap included in your code. Make a basic main function that does a test run for each of the 3 functions above.
Explanation / Answer
These 4 questions are very big to solve. I am giving solution for the first one. Reamining questions you can post seperately.
ANSWER 1:
def heap_sort( mylist ):
# convert mylist to heap
length = len( mylist ) - 1
leastParent = length / 2
for i in range ( int(leastParent), -1, -1 ):
move_Down( mylist, i, length )
# flatten heap into sorted array
for i in range ( length, 0, -1 ):
if mylist[0] > mylist[i]:
swap( mylist, 0, i )
move_Down( mylist, 0, i - 1 )
def move_Down( mylist, fir, last ):
lar = 2 * fir + 1
while lar <= last:
# right child exists and is larger than left child
if ( lar < last ) and ( mylist[lar] < mylist[lar + 1] ):
lar += 1
# right child is larger than parent
if mylist[lar] > mylist[fir]:
swap( mylist, lar, fir )
# move down to lar child
fir = lar;
lar = 2 * fir + 1
else:
return # force exit
def swap( A, x, y ):
tmp = A[x]
A[x] = A[y]
A[y] = tmp
li=[8,5,3,1,9,6,0,7,4,2,5]
heap_sort(li)
print(li)
Time Complexity of this Solution is:
Best O(nlog(n));
Average O(nlog(n));
The worst case run time for this function must be O(nlog(n))
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.