6. Merge Bubble Sort: a) How does the merge bubble sort break the array into sub

Question

6. Merge Bubble Sort: a) How does the merge bubble sort break the array into sublists? b) What does it need to use for each sublist and then what does it do with all of the sublists? c) What is the Big-O notation for this sort? 7. Merge Sort: a) How does the merge sort use recursion to break the array into sublists? b) What happens to each of these sublists to get the final sorted list? c) What is the best and worst case Big-O notation for this sort? 8. External File Sort: a) Why are three files used to implement this sort and how is each used? b) What is its major advantage and its major disadvantage over internal sorts? 9. Quick Sort: a) How do you select the pivot value and how is it used to create two sublists? b) When every sublist of 1 or 2 elements is sorted, what assertion ensures that the entire array must be sorted? c) What is the best and worst case Big-O notation for this sort? d) What are the kinds of lists for which it is best? 10. Heap Sort: a) How is the initial array of data values conceptually represented? b) what are the two subscripts that are used to access the two children of node #X? c) What is the definition of a heap? d) Explain the basic process of filtering," "swapping," and "freezing" to get each element of the array in its final location.

Explanation / Answer

6a) I haven't came across the Merge Bubble sort but there are bubble sort and merge sort. Probably in Merge Bubble sort, at the tiem of merging partitions the bubble sort is used.

7a) Merge sort use recursion to find the middle of the list

and keeps on divding the list into two halves until each comprising 1 element

7b) A list of 1 element is supposed sorted. Now o n merging, the first element of both lists is compared. In ascending order, the smaller element among two becomes a new element of the sorted list. This procedure is repeated until all the sublists are combined into one big list.

7c) The best , average and worst case have the same time complexity O(N*log(N)) in merge sort. In comparsion with best case and worst case, on merging the list the number of comparisons in each merge step to N/2 compare to N-1 in worst case. Hence, the time complexity is same overall.

8b) The main advantage of external sort is that can handle huge amounts of data that do not fit into the main memory of a computing device (RAM) at a time and instead they must reside in the external memory (hard drive).

The main disadvantage of external sort to internal sort that it is quite slow compare to internal sort.

9a) Different ways to pick pivot in quickSort that.

The element smaller than pivot are in one array and greater than pivot in one array and the process continues recursively.

9b) best case - O(nLogn), The best case occurs when the partition process always picks the middle element as pivot.

worst case - O(n2), worst case occurs when the partition process always picks greatest or smallest element as pivot

9c) quickSort best in case the list is unordered not sorted because worst case occur when the array is already sorted in increasing or decreasing order and you are selecting pivot as first or last element of the partition.

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.