Algorithm Comparison Sorting Answer with \"Yes\", \"No\", or \"Don\'t know\". Ex

Question

Algorithm Comparison Sorting

Answer with "Yes", "No", or "Don't know".

Explanation please!

Quicksort is asymptotically faster than bubblesort In the worst case Yes No Don't know On average Yes No Don't know Quicksort is asymptotically slower than mergesort In the worst case Yes No Don't know On average Yes No Don't know To sort 8 numbers, it is necessary to make at least 16 comparisons Yes No Don't know comparisons Yes No Don't know 18 comparisons Yes No Don't know To find 2 heavier coins among 14 same coins using lever scales it is necessary to make at least 4 comparisons Yes No Don't know 5 comparisons Yes No Don't know To find 2 heavier coins among 15 same coins using lever scales it is necessary to make at least 4 comparisons Yes No Don't know 5 comparisons Yes No Don't know

Explanation / Answer

15. Quick Sort aymtotically faster than bubbl sort.

Quicksort :

quicksort uses divide-and-conquer, and so it's a recursive algorithm

Here we don't have the merge step, at the end all the elements are in the proper order.

Bubblesort:

In the bubble sort, the consecutive elements of the table are compared and if the keys of the two

elements are not found in proper order, they are interchanged. It starts from the beginning of the

table and continue till the end of the table.

In Worst Case: Both sorting algorithm have same runtime , but considering the case of large data,

Yes, Quick sort is faster than Bubble Sort

Runtime for the algorithms are

·Quicksort: O(N^2)

·Bubble Sort:O(N^2)

In the average case: Yes, Quick Sort is asymptotically faster than Bubble Sort

·Bubblesort:O( n^2)

This means that Quicksort will tend to be faster than Bubblesort.

16. Quick Sort asymptotically slower than Merge Sort:

Quicksort in requires little additional space and exhibits good cache locality, and this makes it faster than merge sort in many cases.We can easily avoid quicksort’s worst-case run time of O(n2) by picking an appropriate choice of the pivot

There fore

In Worst Case: Yes, Quick sort is bit slower than Merge Sort. But in most real world case by using appropriate pivot element Quick sort is at par with Merge Sort and Quick sort is mostly used.

In Average Case: No, Quick Sort is not slower than Merge Sort. Both runtime is same. As said earlier, Quick sort is preferred.

17. To sort 8 numbers, it is necessary to make : 16 Comparisons

18. To find 2 heavier coins among 14 coins using lever scales it is necessary to make atleast : 4 Comparisons

19. To find 2 heavier coins among 15 coins using lever scales it is necessary to make atleast : 4 Comparisons

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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