Explore topic-wise InterviewSolutions in .

Right answer is (a) It is a non comparison based integer sort

The explanation is: Radix sort is a non-comparison based integer sort. It SORTS the given data by GROUPING KEYS which share the same SIGNIFICANT position VALUE.

Correct ANSWER is (d) FORWARD radix SORT

The explanation is: Forward radix sort combines the QUALITIES of MSD and LSD radix sort. The sorting is done by separating the strings into groups.

Right option is (a) most SIGNIFICANT digit

To explain: MSD stands for Most Significant Digit. It is named so because in this ALGORITHM the PROCESSING begins from the most significant digit.

Right option is (d) 0

Easiest explanation - As MSD RADIX sort is an EXAMPLE of non comparison sort so it is able to sort an array WITHOUT making any comparison. So the answer should be 0.

Right option is (a) False

The best explanation: LSD radix is not an in-place sorting algorithm. It needs extra memory to STORE the elements in bucket and its worst case space complexity is O(W + R).

Right answer is (a) FORWARD radix sort

Easy explanation - Forward radix sort COMBINES the advantages of LSD and MSD radix sort. Forward radix sort INSPECTS a COMPLETE horizontal strip at a time just like LSD radix sort.

The CORRECT ANSWER is (c) LSD radix SORT

For explanation: LSD radix requires only w passes to sort a fixed-LENGTH string, where w is a length of the strings. So, LSD radix sort is best suited to sort a huge database on a fixed-length key FIELD.

The correct choice is (b) False

The BEST I can explain: LSD radix sort is faster than comparison SORTS when the word size is LESS than logn. But LSD radix sort runs slowly for elements with larger word size and SMALLER radix.

Right answer is (d) LSD radix sort

Easiest explanation - In LSD radix sort after sorting the MULTIPLE ELEMENTS with the same key will be in the same ORDER as they were in the INPUT array. So LSD radix sort is stable sort.

The correct answer is (b) LSD radix SORT is a COMPARISON sorting algorithm

The EXPLANATION is: LSD radix sort uses bucket sort for GROUPING the KEYS based on the digits at that value. And as it grouped the keys based on the digits at that values, it is integer sorting algorithm.

Right choice is (b) O(wn)

Easiest explanation - Time COMPLEXITY of LSD radix sort DEPENDS UPON the word SIZE and the number on items. It runs in O(wn) time in worst case, where n is the number of inputted elements and W is the number of digits in the largest number.

Correct CHOICE is (d) LSD radix sort

The best explanation: In Distribution sort the inputted values are distributed to multiple INTERMEDIATE STRUCTURES which are then combined and placed on the OUTPUT. And LSD radix sort distributes values into buckets based on the digits within values, so it is a distribution sort.

The CORRECT answer is (b) O(N+k)

The explanation is: Time COMPLEXITY of pigeonhole sort is O(n+k). It has two loops. ONE of the loops runs from 0 to range(k) and the other one runs from 0 to n so the time complexity becomes O(n+k).

The correct option is (b) false

Easy EXPLANATION - PIGEONHOLE sort requires space of O(n+k). So it does not qualify to be an in PLACE SORTING ALGORITHM.

Correct OPTION is (a) true

The best I can explain: PIGEONHOLE sort is an example of a stable SORTING algorithm. It is because the elements with identical values appear in the same order in the output array as they were in the INPUT array.

The correct OPTION is (d) pigeonhole

Easiest explanation - The auxiliary ARRAY used in pigeonhole SORTING is called pigeonhole. It is used to store every element in its CORRESPONDING hole.

Right choice is (d) O(n+k)

Best explanation: PIGEONHOLE sort algorithm requires two arrays. The FIRST one is REQUIRED to store the input elements so its size is n. The second one is the pigeonhole array and has a size equal to range k. OVERALL space complexity BECOMES O(n+k).

The CORRECT choice is (c) when range of input is COMPARABLE to the NUMBER of elements

Explanation: Pigeonhole sort is a non-comparison BASED sort. It is most efficient in the case where the number of elements are comparable to the input range.

The correct option is (d) pigeonhole sort

To EXPLAIN: Heap sort, merge sort and quick sort are EXAMPLES of comparison sort as it NEEDS to compare ARRAY elements in order to sort an array. Whereas pigeonhole sort is a non-comparison based sort.

Correct CHOICE is (d) 0

The best I can explain: As PIGEONHOLE sort is an example of a non-comparison sort so it is able to sort an ARRAY WITHOUT making any comparison. So 0 comparisons are required.

Right option is (a) True

The explanation is: Sleep SORT is an in-PLACE sorting technique as most of its major steps takes place in the BACKGROUND. So it does not REQUIRE auxiliary space to sort the input.

Right answer is (b) SLEEP SORT

The best explanation: Sleep sort is most closely related to the operating system. It is because most of the major STEPS of this algorithm TAKES place at the core of OS.

The CORRECT CHOICE is (C) any input element is positive

Easy explanation - Sleep sort gives a sorted output when the array elements are positive. But when any other case than this occur out of the above GIVEN cases then we MAY not see a correct output. This makes sleep sort very unreliable sorting technique.

The correct choice is (b) O(1)

Explanation: All the MAJOR PROCESSES involved in sleep SORT TAKES place internally in the OS. So it does not require any auxiliary space to sort the ELEMENTS.

The correct OPTION is (d) No SORTING algorithm is preferred

The best I can explain: Sleep SORT is not preferred over any of the given sorting algorithms as sleep sort does not guarantee a correct OUTPUT every time. So sleep sort is not a RELIABLE sorting technique.

Right choice is (c) O(n log n + MAX(input))

EXPLANATION: As the SLEEP() function creates multiple THREADS by using PRIORITY queue which takes n log n time for insertion. Also the output is obtained when all the elements wake up. This time is proportional to the max(input). So its time complexity is approximately O(n log n + max(input)).

The CORRECT answer is (C) it requires multithreading process

The explanation is: Sleep sort requires multithreading process for making the elements to sleep. This process happens in the background at the core of the OS and so cannot be COMPILED on an online compiler.

The CORRECT option is (a) making elements to SLEEP for a time that is proportional to their magnitude

Explanation: In sleep sort each element is made to sleep for a time that is proportional to its magnitude. Then the elements are PRINTED in the order in which they WAKE up.

Right option is (d) 0

Best explanation: SLEEP SORT makes DIFFERENT elements of the array to sleep for an amount of time that is PROPORTIONAL to its MAGNITUDE. So it does not require to perform any comparison in order to sort the array.

Right choice is (a) negative NUMBERS

Easiest EXPLANATION - Sleep sort algorithm does not WORK for negative numbers. It is because thread cannot sleep for negative amount of TIME.

The correct option is (c) O(infinity)

For EXPLANATION: There is no upper bound to the worst case of this ALGORITHM. It can go on to TAKE very large amount of time if the array has many elements. So the worst case of this algorithm can be TAKEN as O(infinity).

Correct ANSWER is (b) O(n)

Easiest explanation - Best case TIME complexity of BOGOSORT occurs when the input ARRAY is already sorted. So in such a case we only need to check whether all the elements are sorted which can be done in O(n) time.

Correct answer is (b) O(1)

EXPLANATION: Bogosort algorithm do not REQUIRE any extra space for SORTING the input array. Thus its AUXILIARY space requirement is O(1).

The correct option is (c) donkey sort

For EXPLANATION: BOGOSORT is also known by names LIKE stupid sort, monkey sort, permutation sort, slow sort and SHOTGUN sort.These names are particularly chosen due to its INEFFICIENT algorithm.

The correct choice is (b) O(n^2)

To explain: In gnome SORT the loop has to take one step backwards EVERY time any adjacent pair of ELEMENTS is out of PLACE which causes it to have time complexity of O(n^2) on an average.

Right CHOICE is (a) O(1)

To explain: Auxiliary space used by gnome SORT is O(1) as it does not use any EXTRA space for MANIPULATING the INPUT. Thus it also qualifies as an in place sorting algorithm.

Right OPTION is (c) gnome sort and merge sort

The best EXPLANATION: Gnome sort and merge sort are STABLE sorting algorithms as the elements with IDENTICAL values appear in the same order in the output array as they were in the input array when any of these sorting algorithms are implemented.

Right answer is (a) Single loop

The best I can explain: In this SORTING ALGORITHM the variable representing the INDEX number is not incremented in case the adjacent pair of ELEMENTS are out of place. In such a case its VALUE is decremented instead. Thus it is able to implement sorting using a single loop.

Right choice is (b) Stupid sort

Best EXPLANATION: GNOME sort was ORIGINALLY NAMED as stupid sort but later on it GOT renamed as gnome sort.

The correct OPTION is (b) O(n LOG n) and O(n)

Explanation: Best case complexity for comb SORT and bubble sort is O(n log n) and O(n) respectively. It occurs when the INPUT array is already sorted.

The CORRECT option is (b) False

Easy explanation - Comb sort is not a STABLE sorting ALGORITHM as it does not sort the REPEATED elements in the same ORDER as they appear in the input.

The correct answer is (d) 4 and 5

Best explanation: Comb sort takes 1 iteration LESS as compared to BUBBLE sort as it makes USE of variable GAP value WHEREAS bubble sort uses a constant gap value of 1.

Right answer is (a) O(1)

The explanation is: Auxiliary space used by comb SORT is O(1) as it does not USE any extra space for MANIPULATING the input.

Right option is (c) 2

Easy EXPLANATION - Initially the GAP VALUE will be 6. For the first iteration, it will be 6/1.3=4 then 4/1.3=3 for second iteration and 3/1.3=2 for the third iteration.