MadeEasy Test Series: Algorithms - Sorting

Question

Consider the following code executed on an n-element array A such that each element i an A satisfies the
condition 0 ≤ A[i] < 1. The code also uses an auxiliary array, B[0 to n – 1].
Random-Sort (A)
{
1. n ← Length [A]
2. For i ← 1 to n
3. do insert A[i] into list B [ ⌊n A[i]⌋ ]
4. For i to n – 1
5. do sort list B[i] with
6. Concatenate the list B[0], B[1], ..., B[n – 1] together in order.
}
Which algorithm will be placed in the blank at line 5 for sorting (stable) so that the code will give minimum
time complexity?

Answer 1

See this line ""Concatenate the list B[0], B[1], ..., B[n – 1] together in order"".

This Algorithm is implementing a bucket sort, in which the input is divided into fixed length buckets. 

Take for example => 34,109,349,233,567,895,234,456,245,.......

Now this input size can be divided into fixed length buckets of size 100 each and each bucket is sorted particularly, then as the last line suggests, concatenate all the buckets. Main thing lies that which algorithm are we going to use to sort a particular bucket.

Best case lies, when elements are uniformly distributed between the buckets.

Worst case lies, when all the elements are multiplexed into a single bucket. So, for a large input, sorting algorithm for this one bucket can lead to worst case sorting.

Bucket sort always uses stable sorting algorithm for sorting a particular bucket as a subroutine.

There are stable sorting algorithms available => Merge sort , Insertion sort , Bubble sort .

A). Merge sort Worst case O(N log N).

B). Insertion sort Worst case O(N²).

C). Bubble sort Worst case O(N²).

Now, stable sorting algorithm gives minimum WC complexity, is Merge sort.

Comments

But we always prefer insertion sort .Even the qus is asking about min time complexity means what expected or worst ?

---

Yes, ẃe do use insertion sort, but what if there are large number of elements in a particular bucket, then insertion sort will incur worst case .

I think we must consider the best algorithm, which gives min. C. in the worst case .

---

what if there are large number of elements in a particular bucket

Bucket sort assumes that the input is generated by a random process that distributes elements unformaly and independently over the interval [0,1) so we do not except many numbers to fall into each bucket.

To produce the output ,we simply sort numbers in each bucket and then go through the bucket in order listing the elements in each.

Reference:CLR

 Check this ones 

 http://cs.stackexchange.com/questions/9876/worst-case-analysis-of-bucket-sort-using-insertion-sort-for-the-buckets

---

okk ! Since, the code is using  B[0], B[1], ..., B[n – 1] buckets, hence we have to size the buckets like we don't expect many numbers to fall into each bucket and hence IS will give min. time complexity .

In the question, we are provided with N buckets, hence bucket sort will distribute elements such that each buckets has less elements, and then IS is preferred .

But, if the code used a single bucket, then we would have preferred merge sort , right ?

---

The worst case for bucket sort occurs when the all inputs falls into single bucket , for example. Since we use insertion sort for sorting buckets and insertion sort has a worst case of $\large O(n^2 )$, the worst case runtime for bucket sort is $\large O(n^2 )$.

So if worst is the only concern here then  your assumption is correct.We can use only any algo with worst case complecity for ex. merge sort $\large O(nlogn)$ (stable) and heap sort $\large O(nlogn)$(but not stable) which will give worst case of bucket sort $\large O(nlogn)$.

---

yes, i thought question is asking for WC only, when all are multiplexed into a single bucket, so merge sort is perfect for this .

---

yes.

---

@ManojK, @Kapilp,  We prefer IS over other sorting algo if list contains less elements right ??
But, can you please tell something about this less elements, I mean range of this "less elements". I am asking this because in above link it is mentioned that we prefer IS if list contains 20 or less elements. But here we are not given any hint about size of bucket (If it is 30 or 40 or 50 or more but not less than 20 then other stable sorting ago(merge )  will be used.   

---

Buckets are implemented by a queue. So, if the algorithm is designed so nicely that elements are uniformly distributed between the buckets . what I meant by "so nicely " is that every bucket gets small number of elements, then yes IS can be used in linear time.

But, what if algorithm didn't work nicely,means it multiplexes all the elements into a single bucket . Then complexity of BS = complexity of sorting particular bucket. Now suppose this bucket has small elements preferred for IS but in reverse order, then insertion sort gives the worst case.

Hence, we prefer merge sort.

So, actually there are many stable sorting algo. But among them which gives the minimum time complexity ?