Exercises

1.   Consider the sequence of integers

   

   For each of the following sorting algorithms, draw a sequence of diagrams that traces the execution of the algorithm as it sorts the sequence S: straight insertion sort, binary insertion sort, bubble sort, quick sort, straight selection sort, heapsort, merge sort, and bucket sort.

2.   Draw a sequence of diagrams that traces the execution of a radix-10 sort of the sequence

   

3. For each of the sorting algorithms listed in Exercises  and  indicate whether the sorting algorithm is stable.
4. Consider a sequence of three distinct keys . Draw the binary decision tree that represents each of the following sorting algorithms: straight insertion sort, straight selection sort, and bubble sort.
5.   Devise an algorithm to sort a sequence of exactly three elements. Make your algorithm as efficient as possible.
6. Prove that the swapping of a pair of adjacent elements removes at most one inversion from a sequence.
7. Consider the sequence of elements . What is the maximum number of inversions that can be removed by the swapping of a pair of distinct elements and ? Express the result in terms of the distance between and : .
8. Devise a sequence of keys such that exactly eleven inversions are removed by the swapping of one pair of elements.
9. Prove that binary insertion sort requires comparisons.
10.   Consider an arbitrary sequence . To sort the sequence, we determine the permutation such that

    

    Prove that bubble sort requires at least p passes where

    

11. Modify the bubble sort algorithm (Program ) so that it terminates the outer loop when it detects that the array is sorted. What is the running time of the modified algorithm? Hint: See Exercise .
12. A variant of the bubble sorting algorithm is the so-called odd-even transposition sort . Like bubble sort, this algorithm a total of n-1 passes through the array. Each pass consists of two phases: The first phase compares with and swaps them if necessary for all the odd values of of i. The second phase does the same for the even values of i.
    1. Show that the array is guaranteed to be sorted after n-1 passes.
    2. What is the running time of this algorithm?
13. Another variant of the bubble sorting algorithm is the so-called cocktail shaker sort . Like bubble sort, this algorithm a total of n-1 passes through the array. However, alternating passes go in opposite directions. E.g., during the first pass the largest item bubbles to the end of the array and during the second pass the smallest item bubbles to the beginning of the array.
    • Show that the array is guaranteed to be sorted after n-1 passes.
    • What is the running time of this algorithm?
14.   Consider the following algorithm for selecting the largest element from an unsorted sequence of of n elements, .
    1. If , sort S and select directly the largest element.
    2. Otherwise n>5: Partition the sequence S into subsequences of length five. In general, there will be subsequences of length five and one of length .
    3. Sort by any means each of the subsequences of length five. (See Exercise ).
    4. Form the sequence containing the median values of each of the subsequences of length five.
    5. Apply the selection procedure recursively to find the median element of M. Let m be the median of the medians.
    6. Partition S into three subsequences, . such that all the elements in L are less than m, all the elements in E are equal to m, and all the elements of G are greater than m.
    7. If then apply the procedure recursively to select the largest element of L; if , the result is m; otherwise apply the procedure recursively to select the largest element of G.
    1. What is the running time of this algorithm?
    2. Show that if we use this algorithm to select the pivot the worst-case running time of quick sort is .
15.   Show that the sum of the heights of the nodes in a complete binary tree with n nodes altogether is n-b(n), where b(n) is the number of ones in the binary representation of n.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.