Consider the basic implementations of sorting algorithms discussed in class and

Question

Consider the basic implementations of sorting algorithms discussed in class and during lab. Circle true/false for each of the following statements below. Selection sort is always O(N^2). Quick sort is always O(N log_2N). Bubble sort O(N) in the best case. Heap sort uses a binary search tree to sort data. Merge sort uses more memory than quick sort. Merge sort O(N log_2N) in the best case. Bucket sort uses a linked list to store sorted data. Bucket sort is the fastest algorithm for sorting strings.

Explanation / Answer

Selection sort is always O(N^2) : True

Quick Sort always O(NlogN) : False
       Worst case of Quick Sort = O(N^2)

Bubble Sort O(N) is the best: True
       If array is already sorted then this is the best case

Heap Sort user more memory than quick sort: False
  
Merge Sort used more memory than Quick Sort: True

       Merge Sort uses O(N) extra memory

Bucket sort uses a linked list to store data: true

Bucket sort is the fastes algorithm for sorting strings: False
   Bucket sort is mainly useful when input is uniformly distributed over a range.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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