Could someone please help me with Question 8. Modify it so that it uses quicksor

Question

Could someone please help me with Question 8.

Modify it so that it uses quicksort until it reaches the LOWER_BOUND, which is essentially an arbitrary number that can either be hardcoded or asked for at run-time. Basically, you "count" the total number of values in the array, the decrement a counter until you reach lower than LOWER_BOUND. Once you reach this point, you want to have it sort using insertion, as this is a faster method for partially sorted arrays.

7. Modify quicksort) to use insertion sort if the sublist has fewer than LOWER BOUND elements for some constant LOWER_BOUND and use quicksort otherwise 8. The preferred alternative to the approach in Exercise 7 suggested in the text was to ignore all sublists with fewer than LOWER BOUND elements, not splitting them further. When execution of the quicksort algorithm terminates, simply sort the list using insertion sort. Modify quicksortO to incorporate this modification.

Explanation / Answer

#include <stdio.h>

void swap ( int* a, int* b )
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int l, int h)
{
    int x = arr[h];
    int i = (l - 1);

    for (int j = l; j <= h- 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            swap (&arr[i], &arr[j]);
        }
    }
    swap (&arr[i + 1], &arr[h]);
    return (i + 1);
}

void quickSortwithInsertion (int arr[], int l, int h)
{
    int stack[ h - l + 1 ];

    int top = -1;

    stack[ ++top ] = l;
    stack[ ++top ] = h;

    while ( top >= 0 )
    {
        h = stack[ top-- ];
        l = stack[ top-- ];

        int p = partition( arr, l, h );

        if ( p-1 > l )
        {
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        }

        if ( p+1 < h )
        {
            stack[ ++top ] = p + 1;
            stack[ ++top ] = h;
        }
    }
}

void print( int arr[], int n )
{
    int i;
    for ( i = 0; i < n; ++i )
        printf( "%d ", arr[i] );
}

int main()
{
    int arr[] = {4, 3, 5, 2, 1, 3, 2, 3};
    int n = sizeof( arr ) / sizeof( *arr );
    quickSortwithInsertion( arr, 0, n - 1 );
    print( arr, n );
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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