1. Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting time-of-transaction ordering to check-number ordering is therefore the problem of sorting almost-sorted input. What sorting algorithm would work best for this case?

   Insertion sort algorithm Merge-Sort algorithm Heap-Sort algorithm Quick-Sort algorithm Counting-Sort algorithm

2. In Quick-Sort, the last element is chosen as a pivot element. If a list is sorted already, a pivot will be always the largest number in the list and the algorithm runs O(n²). How can we solve this problem?

   Use divide-and-conquer algorithm Use incremental algorithm Use randomized algorithm Use dynamic programming None of the above

3. Suppose we should write a program to sort an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. What sorting algorithm should we consider to use for this scenario?

   Quick sort Bucket sort and Counting sort Bucket sort and Radix sort Bucket sort and Insertion sort None of the above

4. Suppose we should write a program to sort in place, using no more than a constant amount of storage space in addition to the original array. What sorting algorithms should we avoid?

   Counting sort Radix sort Bucket sort Merge sort All of the above

5. How many comparisons are required to sort an array of length 10 if insertion sort algorithm is used and the array is already sorted?

   9 10 15 20 None of the above