Reference no: EM133220399

1. The Bubble Sort implementation has the following inner for loop: for (int j=n-1; j>i; j--) Consider the effect of replacing this with the following statement: for (int j=n-1; j>0; j--) Would the new implementation work correctly? Would the change affect the asymptotic complexity of the algorithm? How would the change affect the running time of the algorithm?

2. When implementing Insertion Sort, a binary search could be used to locate the position within the first i - 1 elements of the array into which element i should be inserted. How would this affect the number of comparisons required? How would using such a binary search affect the asymptotic running time for Insertion Sort?

3. Figure 7.5 shows the best-case number of swaps for Selection Sort as Θ(n). This is because the algorithm does not check to see if the ith record is already in the ith position; that is, it might perform unnecessary swaps.

a. (pseudo-code only) Modify the algorithm so that it does not make unnecessary swaps.

b. What is your prediction regarding whether this modification actually improves the running time.

4. Recall that a sorting algorithm is said to be stable if the original ordering for duplicate keys is preserved. Of the sorting algorithms Insertion Sort, Bubble Sort, Selection Sort, Shellsort, Mergesort, Quicksort, Heapsort, Binsort, and Radix Sort, which of these are stable, and which are not? For each one, describe either why it is or is not stable. If a minor change to the implementation would make it stable, describe the change.

5. The discussion of Quicksort in Section 7.5 described using a stack instead of recursion to reduce the number of function calls made.

a. How deep can the stack get in the worst case?

b. Quicksort makes two recursive calls. The algorithm could be changed to make these two calls in a specific order. In what order should the two calls be made, and how does this affect how deep the stack can become?