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

1(a) &(b) ::: Bubble sort is a simple sort algorithm where the sort function compares a number with its just adjacent and swaps if the later one is smaller than the previous one.

As for example:

Let us take an array of random numbers :: 0 7 2 5 3 9 6 4

1st it compares 0 and 7 and they are sorted :: 0 7 2 5 3 9 6 4

then 7 and 2 and swaps: 0 2 7 5 3 9 6 4

then 7 and 5 and swaps: 0 2 5 7 3 9 6 4

then 7 and 3 : 0 2 5 3 7 9 6 4

then 7 and 9 are sorted: 0 2 5 3 7 9 6 4

then 9 and 6: 0 2 5 3 7 6 9 4

then 9 and 4: 0 2 5 3 7 6 4 9

This was the 1st set of sorting.

After the 2nd set it becomes : 0 2 3 5 6 7 4 9

After the 3rd set it becomes : 0 2 3 5 6 4 7 9

And so on.. And lastly we get 0 2 3 4 5 6 7 9. This is the sorted array. So, after the #X pass we can not say that up to that Xth position the array is permanently sorted. Those values can not change their position. But we can definitely claim that it is temporarily sorted up to that particular position.

In case of Selection Sort the methodology is completely different.

Here the minimum element is chosen and put in the first position. And from the rest of the array another minimum element is chosen and put into the 2nd position and this process keeps repeating until the whole array is sorted.

As for example,

A random array :: 8 4 0 1 3 7 6

minimum 0 and comes 1st: 0 8 4 1 3 7 6

0 is sorted, minimum from the rest is 1 : 0 1 8 4 3 7 6

0 and 1 sorted, minimmum from rest is 3 : 0 1 3 8 4 7 6 and so on..

Finally, the sorted array comes: 0 1 3 4 6 7 8

So we can say that after #Xth pass the left side of the array up to that position the array is permanently sorted.

(c)

Although in worst case selection sort works better and faster than that of bubble sort but we can say bubble sort algorithm is a more stable algorithm than that of selection sort. As we know we call those algorithms stable If two objects with equal keys appear following a specific order while giving input then it should come in that particular order in output too. But, selection sort algorithm is unstable. So bubble sort is better in this case.

While comparing with insertion sort, in bubble sort the bigger elements are sent to the end of the array as early as possible. This is a key difference in operation between the two algorithms in which bubble sort is better than insertion sort.

7.(a) Merge sort is basically a divide and conquer algorithm. Algorithm states to divide the array and into two parts and calls itself for the two parts and keep dividing until it reaches to a single element(which is considered as automatically sorted). It uses the recursive mechanism to reach to that single element array.

The process is:

if left index < right index

then, mid = left index + ( right index -1 ) / 2

Thus, it reaches to single element parts.

(b) After dividing the array into smallest units merging starts with comparison process.

The algorithm compares the 1st element of the 1st subarray with the 1st element of the 2nd and arranges it in a sorted manner.

example:

Say, 38 27 43 3 9 82 10 are single element sub arrays. now units become as

27 ,38 3 ,43 9 ,82 10

now 3 and 27 are compared AND 38 and 43 are compared.

3,27,38,43

and 9 and are compared,

9,10,82

now 3 and 9 , 27 and 10, 38 and 82 and 43 and 82 are compared and results:

3 ,9 ,10, 27, 38, 43 ,82 which is sorted.

(c) worst case time complexity: O(n log(n))

best case :(n log(n))

9. (a) We can select any value as pivot. But selecting the pivot element we have to make sure its correct position.And we have to make sure one side of the pivot should keep the sublist of the elements smaller than that and another side the sublist contains all the bigger elements.

(c) best case : (n log(n))

worst case : O(n^2)

(d) The lists for which we can divide it into two nearly equal pieces. this case occurs if the subarray has an odd number of elements and the pivot is right in the middle after partitioning. Then it becomes similar as merge sort.

4. (a) A list of bucket is created. Elements are inserted to buckets. And each bucket is individually sorted using insertion sort. And then all the sorted buckets are concatinated again.

(b) It works best for data which are uniformly distributed.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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