edited by
3,432 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?

edited by

1 Answer

Best answer
7 votes
7 votes

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

Related questions

0 votes
0 votes
0 answers
2
Abhishek Kumar 38 asked Dec 19, 2018
611 views
Which of the following sorting algorithm represented by above code?
0 votes
0 votes
2 answers
4
Somoshree Datta 5 asked Oct 20, 2018
1,583 views
Consider the following scenario during insertion sort when the array looks like the following:{25,75,95,125,80,5,10}The number of comparisons that it will further take fo...