Aptitude Basic Questions on Sorting

1 .In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?

A. 1
B. n - 1
C. n log n
D. n^2

2 .Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?

* A. O(n log n) sorts
* B. Divide-and-conquer sorts
* C. Interchange sorts
* D. Average time is quadratic.

3 . Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

* A. 21
* B. 41
* C. 42
* D. 43

4 .Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

1 2 3 4 5 0 6 7 8 9

Which statement is correct? (Note: Our selectionsort picks largest items first.)

* A. The algorithm might be either selectionsort or insertionsort.
* B. The algorithm might be selectionsort, but could not be insertionsort.
* C. The algorithm might be insertionsort, but could not be selectionsort.
* D. The algorithm is neither selectionsort nor insertionsort.

5 .Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

2 4 5 7 8 1 3 6

Which statement is correct? (Note: Our selectionsort picks largest items first.)

* A. The algorithm might be either selectionsort or insertionsort.
* B. The algorithm might be selectionsort, but it is not insertionsort.
* C. The algorithm is not selectionsort, but it might be insertionsort.
* D. The algorithm is neither selectionsort nor insertionsort.

6 .When is insertionsort a good choice for sorting an array?

* A. Each component of the array requires a large amount of memory.
* B. Each component of the array requires a small amount of memory.
* C. The array has only a few items out of place.
* D. The processor speed is fast.

7 What is the worst-case time for mergesort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

8 What is the worst-case time for quicksort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

9 .Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?

* A. The array elements form a heap.
* B. Elements in each half of the array are sorted amongst themselves.
* C. Elements in the first half of the array are less than or equal to elements in the second half of the array.
* D. None of the above.

10 .Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10

Which statement is correct?

* A. The pivot could be either the 7 or the 9.
* B. The pivot could be the 7, but it is not the 9.
* C. The pivot is not the 7, but it could be the 9.
* D. Neither the 7 nor the 9 is the pivot.

11 .What is the worst-case time for heapsort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

12.Suppose you are given a sorted list of N elements followed by f(N) randomly ordered elements.How would you sort the entire list if
* A. f(N)=O(1)
* B. f(N)=O(logN)
* C. f(N)=O(N^1/2)
* D. How large can f(N) be for the entire list still to be sortable in O(N) time?

13.Prove that any algorithm that find an element X in a sorted list of N elements requires Omega(log N) comparisons.

14.Prove that sorting N elements with integer keys in the range 1 < Key < M
takes O(M + N) time using bucket sort.

15.Suppose you have an array of N elements,containing only 2 distinct keys, true and false.Give an O(N) algorithm to sort the array.

16.Prove that any comparison based algorithm to sort 4 elements requires atleast 5 comparisons

17. In how many ways can 2 sorted arrays of combined size N be merged?

18.Show that binary insertion may reasonably be expected to be an O(n log n) sort.

19.You are given two sets of numbers Xi and Yj , where i and j run from 1 to N.
Devise an algorithm to find the M largest values of Xi −Yj . This algorithm should
not be quadratic in N, though it is permitted to be quadratic in M.
You should regard N as being of the order of 20,000 and M as being of the order
of 1,000.


20.If 1024 numbers are drawn randomly in the range 0–127 and sorted by binary
insertion, about how many compares would you expect?