1. Bubble Sort: the difference between which items are in order after pass #x? b

Question

1. Bubble Sort: the difference between which items are in order after pass #x? bubble: selection b) What items are compared and possibly swapped in the bubble sort? c) What aspect of the bubble sort makes it more efficient than the insertion or selection sort for some lists? 2. Shell Sort: a) Which other quadratic sort does the Shell Sort mimic? b) What happens to the gap between numbers after all numbers separated by a given gap are in order? c) What does this sort accomplish better than the quadratic sorts by using different gaps? 3. Pointer Sort: a) How does this sort use pointers to sort an array of objects? b) For what type of data values is it the preferable one to use? 4. Bucket Sort: a) How does this sort use buckets to sort an array of numbers? b) For what type of data values is it the preferable one to use? 5. Radix Sort: a) If the radix sort is O(kn), what would the constant be for 16-bit binary numbers? b) How does the radix sort differ from all of the others for lots of large numbers? c) In what order the digits are accessed?

Explanation / Answer

Question 1 (Assuming we are sorting in ascending order)
a. In Bubble sort, after #X iterations, the top #X largest elements bubble up and are found towards the end of the array (This sorting technique Bubbles up the largest elements after each iteration).
In Selection sort, after #X iterations, the #X smallest elements are already selected and placed in the beginning of the array(Selects the Smallest elements one by one and places them in the front of the array).
b. Bubble sort compares each pair of adjacent items and swaps them if they are out of order. There could be O(N2) swaps in the worst case (When the array is reverse)
c. Bubble sort is good for some lists that are almost sorted with only a few elements out of order and as close to their actual position (in terms of actual sorted order) Here, the time complexity will come down to O(N), whereas selection sort will still till take O(N2).

Question 2
a. Shell sort mimics insertion sort. Both shell sort and insertion sort work by exchanging items that are far apart.
b. When the numbers seperated by given gap are in order, the size of the gap would have been reduced to 0. That is the terminating condition of the algorithm.
c. By using different gaps, unnecessary swaps are avoided and a swap is only made when actual place of the number is found.

Question 3
a. A pointer sort uses a temporaty array that contains pointers to an array of items to be sorted. In a Pointer sort, there are two arrays:

(Note: We can use any sorting algorithm for sorting using pointer technique)

b. When data values to be sorted are too heavy (Objects with sub objects) or complex instead of regular numbers or strings, it becomes an overhead to perform many swaps of these objects. Pointer sort helps remove this by swapping pointers(addresses) instead of the objects.

Question 4
a. Lets go step by step here

b. Bucket sort is preferable to use when input data (preferably numbers) is distributed over a range. e.g., Sorting an array of numbers between 0.0 and 1.0

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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