Quicksort

CISP 430 Assignment 8 Spring 2018 Sorting Algorithms Part 1) Hand-sort the following sequence of numbers. 90 60 30 35 40 45 85 55 50 75 80 70 25 20 65 10 Reference: Please see QuickHeapMergeExamples.pdf posted and use that as a guide. (But please be MUCH neater than the crap I give you.) Create pretty computer-drawn diagrams please. Sort the numbers using the following methods: 1) Heapsort a) redraw the array after every change b) redraw the DATA TREE after every change, (just data changes as a TREE, not program flow) 2) Quicksort a) redraw the array after every change b) redraw the entire complete RECURSION TREE, HW2 style) MergeSort a) 3) redraw the array after every change b) redraw the entire complete RECURSION TREE, HW2 style) You MUST show all your work. Lots of drawing here. Be neat please. You will be graded on format as well as correctness Part 2) What is the time complexity of each algorithm? EXPLAIN YOUR ANSWERS Turn in: Lots of paper with computer-drawn diagrams. Show all your work, including: 1) Redraw the array frequently 2) Draw the recursion trees as directed 3) Indicate each pair of items that are swapped for each step 4) For Heapsort, draw the tree corresponding to the array at each step. Don't forget to perform deletions as well as insertions! Format: Please follow the formatting guidelines posted