a. for sorting a bridge hand? which method is best heapsort, Merge exchange, or
ID: 3744101 • Letter: A
Question
a. for sorting a bridge hand? which method is best heapsort, Merge exchange, or comparison?
b. For sorting a large class grades? which method is best,Heapsort, Merge exchange, or comparison?
c. Fort sortiing a large state license plates? which method is best? Merge exchange, heapsort, or comparison?
please explain the difference between heapsort merge exchange and comparison Thank you
We are sorting lists n symbols in length. The number of steps N to sort a list (and thus the computer time needed for the task) grows (in general) as the list length n growth. Thus N(n) can be modeled as an increasing function of n. Computer scientists can show that depending on the method used for sorting the behavior of N(n) differs and can be described by the expressions in the leftmost column of the table below. (1) Use this information to estimate N values for various methods and for various n and write your estimates in the table below. n 10 n 102 n 106 Comparison Nc(n) = 4n2+10n Merge exchange NM(n)-3.7n * In2(n) Heapsort NH(n)-23nln(n)+0.2nExplanation / Answer
a) for sorting a bridge hand? which method is best heapsort, Merge exchange, or comparison?
Comparison Sort as we can compare the previous card value and the next card value and based on the lower value the cards can be arranged in ascending order
b. For sorting a large class grades? which method is best,Heapsort, Merge exchange, or comparison?
MergeSort
c Fort sortiing a large state license plates? which method is best? Merge exchange, heapsort, or comparison?
HeapSort [Imagine you need to sort a huge list but have very limited memory. And stability is a nice feature for a sorting algorithm, HeapSort is the efficient one in such a case]
please explain the difference between heapsort merge exchange and comparison
Mergesort : Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list
Heapsort : Heapsort is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap. Once the data list has been made into a heap, the root node is guaranteed to be the largest (or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root.
1. Merger sort is stable while heap sort is not stable because operations on the heap can change the relative order of equal items.
2. Heap Sort is more memory efficient and also in place. It doesn't copy the array and store it elsewhere (like merge sort) hence needs less space. It can use used in situations like what's the top 10 numbers from a list of 1 million numbers.
3. Heapsort may make more comparisons than optimal. Each siftUp operation makes two comparisons per level, so the comparison bound is approximately 2n log_2 n. In practice heapsort does only slightly worse than quicksort.
4. Space Complexity
Merge sort : O(n)
Heap sort : O(1) (if done iteratively) But we would have to heapify the array first which will take O(n) time.
5. Merge sort works best on linked lists.
Please let me know in case of any clarifications required. Thanks!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.