1. For the following array x [10] = { 45, 20, 50, 30, 80, 10, 60, 70, 40, 90}, s

Question

1. For the following array x [10] = { 45, 20, 50, 30, 80, 10, 60, 70, 40, 90}, show the contents of x after the function call split Pos = split(x, 0, 9) is executed, and give the value of the array index splitPos (the first is the pivot).

2. Modify quicksort() to incorporate this modification: In quicksort, we do not splitting sublists further when they have fewer than LOWER_BOUND elements for some constant LOWER_BOUND. When execution of the quicksort algorithm terminates, simply sort the whole list using insertion sort.

For question 2, please modify the implementation to fit the requirement.

Here is the code:

Implementing Quicksort Quicksort code // helper function (recursive) template ?typename void quickHelper( T x[l, int first, int last) ( T? if (first last) int pi - split( x, first, last) quickHelper x, first, pi-1); quickHelper( x, pi+1, last // kick-off template void QuickSort( T x[1, int n) i quickHelper ( x, 0, n-1 );

Explanation / Answer

1
       45 20 50 30 80 10 60 70 40 90
       45 20 40 30 80 10 60 70 50 90
       45 20 40 30 10 80 60 70 50 90
       10 20 40 30 45 80 60 70 50 90

2
   template <typename T>
    void insertionsort(T arr[])
    {
        int n = arr.length;
        for (int i=1; i<n; ++i)
        {
            T key = arr[i];
            int j = i-1;
            while (j>=0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j = j-1;
            }
            arr[j+1] = key;
        }
    }

    void quickHelper(T x[], int first, int last){
        if ((last - first) > LOWERBOUND){
             int pi = split(x,first,last);
             quickHelper(x,first,pi-1);
             quickHelper(x,pi+1,last);
        }
        elese {
            insertionsort(x);
        }
    }

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.