Explore topic-wise InterviewSolutions in .

Right CHOICE is (d) exchanging

Easy EXPLANATION - Brick sort uses the method of exchanging as it swaps the ELEMENTS which are out of order. This swapping is done in two PHASES i.e. ODD phase and even phase.

The CORRECT choice is (a) true

To explain: Odd-even sort COMPARES the value of different elements in the array for sorting. Thus, it is a COMPARISON BASED sort.

The correct answer is (a) BRICK SORT

The best EXPLANATION: Brick sort is an in place sorting technique as it only requires constant auxiliary space for manipulating the INPUT ARRAY.

The correct choice is (c) O(1)

The explanation is: In odd-even SORT manipulation is DONE on the input ARRAY itself. So no extra space is required to perform SORTING. Thus it requires constant AUXILIARY space.

The CORRECT choice is (a) Bubble sort

Easy explanation - Odd-EVEN sort is very similar to bubble sort. It works by applying bubble sort in two phases I.e odd PHASE and even phase. In odd phase bubble sort is applied on odd indexed ELEMENTS and in even phase bubble sort is applied on even indexed elements.

Right choice is (C) brick SORT

The explanation is: Odd-even sort is also known by the name of a brick sort. This algorithm was first PROPOSED by Habermann in 1972 and was INITIALLY invented for parallel computation of local interconnection.

Correct option is (d) John GOODMAN

Explanation: (Jacob Goodman – 1975) What is the MAXIMUM NUMBER of flips needed to SORT a permutation of [n] into ascending order?

(Bill Gates and Christos Papadimitriou – 1979) What is the maximum number of flips needed to sort a SIGNED permutation of [n] into ascending order with all positive signs?

Right answer is (d) PERMUTATIONS

Explanation: Here when we FLIPPING the array or stack, we have to take utmost priority to preserve the order of the list so that that sorting doesnt BECOME INVALID. Hence we use permutations, we are ensuring that order MATTERS.

Right choice is (a) FACED down

Best explanation: A varation of this PANCAKE is with burnt pancakes. Here each pancake has a burnt side and all pancakes MUST, in addition, end up with the burnt side on bottom. It is a more difficult version of the regular pancake PROBLEM.

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

Explanation: Most SORTING algorithms try to SORT making the least number of comparisons but in pancake sort we try to sort USING as few REVERSALS as possible. Because the total number of flip operations PERFORMED in a pancake sort is O(n), the overall time complexity is O(n^2).

The CORRECT answer is (a) Flip the GIVEN data

Best explanation: When we use pancake sort, we sort the ARRAY to find the largest, and then flip the array at that point to bring that value to the bottom of the pancake stack. The SIZE of the array that we are dealing with is then reduced and the process continues. Flip operation is the most important function in the pancake sort technique.

Correct answer is (d) 0

Easiest explanation - Bead sort is an EXAMPLE of a non-comparison BASED sorting algorithm. So no comparison is required to be performed in order to sort the array.

The correct choice is (b) false

To EXPLAIN: Bead sort is an example of NON comparison BASED sorting algorithm. This is because it does not compare the value of elements PRESENT in a list in order to sort them.

Correct option is (b) bead sort

To EXPLAIN: Bead sort has an AUXILIARY space COMPLEXITY of O(n2). So it is not an in PLACE sorting ALGORITHM.

The correct CHOICE is (C) O(n^2)

Best EXPLANATION: The auxiliary SPACE complexity of bead sort is O(n^2). It is because an array of size maximum_element*n (maximum_element is the maximum element that is present in the array and n is the size of the array) has to be maintained.

The correct ANSWER is (c) bead sort

For explanation: The algorithm of bead sort was INSPIRED by the natural phenomenon of FALLING objects. THUS, it is also known by the name of gravity sort.

The correct answer is (b) O(n.k)

The best I can EXPLAIN: Worst case space COMPLEXITY of bucket sort is O(n.k). So it is not an in place SORTING algorithm.

Right OPTION is (b) False

Easy explanation - Bucket SORT is not an in place sorting algorithm. It requires an auxiliary SPACE of O(n k) in the worst CASE.

The correct answer is (a) BUCKET sort

The explanation is: Bucket sort is not necessarily a stable sorting ALGORITHM. This is because its stability depends on the stability of the algorithm that we have USED to sort the individual BUCKETS.

Correct answer is (a) O(n + K)

The BEST explanation: Time complexity of bucket sort is O(n+k). It performs BETTER than any comparison BASED sort if there is a uniform input distribution.

Right option is (c) O(n^2)

For EXPLANATION: Time complexity of bucket sort is O(n^2) in the worst case. So if bucket sort does not GET the INPUTS in the DESIRED manner then it BECOMES very inefficient.

The CORRECT ANSWER is (b) Pigeonhole SORT

The best I can explain: Pigeonhole sort is a particular case of BUCKET sort. Bucket sort is also closely related to MSD RADIX sort.

Correct choice is (b) the INPUT is UNIFORMLY distributed

Easiest explanation - Bucket SORT works by distributing the array elements into a number of BUCKETS. So bucket sort is most EFFICIENT in the case when the input is uniformly distributed.

Right choice is (d) input values

For explanation: Time complexity of bucket sort is affected by various FACTORS. These INCLUDE algorithm IMPLEMENTED for sorting individual buckets, number of buckets USED and distribution of input. It doesnot depend on the input VALUE. It can be either positive or negative or zero.

The CORRECT option is (d) 0

To explain: As bucket sort is an example of a non-comparison sort so it is ABLE to sort an array WITHOUT MAKING any comparison. So the ANSWER should be 0.

The correct answer is (C) BIN sort

Explanation: BUCKET sort is also known as bin sort. It is an EXAMPLE of a non-comparison sort.

Right option is (b) quick sort

For explanation: Quick sort requires O(n log n) time for sorting so it TAKES non linear time for sorting whereas COUNTING sort, BUCKET sort and radix sort sorts in linear time.

The correct option is (c) COUNTING SORT

The best I can EXPLAIN: The time complexity of counting sort remains unvaried in all the THREE cases. It is GIVEN by O(n+k).

The correct choice is (b) O(n+k) k=range of input

To explain: Time COMPLEXITY of counting SORT is O(n+k) as counting the occurrence of each element in the input range takes k time and then finding the correct index VALUE of each element in the sorted array takes n time.

Right choice is (B) Counting sort

Best explanation: Counting sort REQUIRES auxiliary SPACE of O(n+k) whereas quick sort, bubble sort and heap sort are in PLACE sorting techniques. Thus counting sort requires most auxiliary space.

Correct answer is (b) COUNTING sort

For explanation: Counting sort is an example of stable SORTING algorithm as the elements with IDENTICAL values APPEAR in the same order in the output array as they were in the input array.

Right CHOICE is (b) False

The BEST I can explain: It is possible to extend the counting sort ALGORITHM for negative numbers as well. In such a case we store the minimum element at the 0th INDEX.

The correct choice is (d) O(n+k) k=range of input

Easiest EXPLANATION - COUNTING SORT uses two EXTRA arrays to get the input array sorted. First array is REQUIRED to store the count of all the elements which fall in the range of input data elements, so its size is k. The second array is required to store the input elements in sorted manner, so its size is n. Thus overall auxiliary space required becomes O(n+k).

The correct choice is (c) counting sort

The BEST explanation: Time complexity of counting sort is given as O(N+K) where n is the number of input elements and k is the range of input. So if range of input is not significantly LARGER than number of elements in the array then it proves to be very efficient.

The correct option is (a) bubble sort

Best EXPLANATION: Bubble sort is not an example of non comparison sort as it NEEDS to COMPARE array ELEMENTS in ORDER to sort an array.

Right answer is (d) 0

The BEST I can EXPLAIN: As counting sort is an example of non comparison sort so it is ABLE to sort an array WITHOUT making any comparison.

The correct answer is (b) 23, 67, 43, 143, 654

Easiest explanation - In the first ITERATION the array is sorted according to the most significant digit I.e. HUNDREDS place value. So the ORDER of elements will be 23, 67, 43, 143, 654.

Correct ANSWER is (b) MSD radix sort

Best EXPLANATION: MSD radix sort is not a stable sort. It is because the elements with identical values do not appear in the same order in the output ARRAY as they were in the input array.

Right choice is (b) False

Easy EXPLANATION - MSD RADIX sort takes non CONSTANT TIME for sorting the input data. So it is not an in place sorting algorithm.

Correct choice is (B) O(n.w)

The best explanation: TIME COMPLEXITY of radix sort is O(n.w). It performs better than quick sort when we have LOG n BITS for every digit.

Right choice is (B) False

The EXPLANATION is: MSD radix sort is not a stable sort WHEREAS LSD radix sort is stable. So when we REQUIRE to preserve the original order then in that case we should prefer LSD radix sort.

Correct choice is (c) it is an in place sorting ALGORITHM

The best EXPLANATION: MSD radix sort TAKES non constant time for sorting the input DATA. So it is not an in place sorting algorithm.