in Algorithms edited by
3,423 views
4 votes
4 votes

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?

in Algorithms edited by
by
3.4k views

1 Answer

7 votes
7 votes
Best answer

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(N2).

C). Bubble sort Worst case O(N2).

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

selected by
by

4 Comments

yes.
1
1

@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.   

0
0
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 ?
0
0

Related questions