Thread: How to optimize quicksort with selectionsort

So adding an if ( n < 200 ) test is too much for you?

No,it's not,but it doesn't work,because this is recursion and I am not good with recursion.
This is my code that doesn't work.

Code:

void quicksort(int *array, int n) {
    int pi;
    if (n < 2)
        return;
    if(n<200){
        selectionsort(array,n);
    }
else{
    pi = partition(array, n);
}
    quicksort(array, pi);
    quicksort(array + pi + 1, n - pi - 1);

}

Once you have used selection sort on the range, there's nothing else to sort in that range, so you should just return.

1. Does your original quicksort function work?
2. Does your selection sort function work?
3. Assuming your answer to #1 and #2 are "yes", what is your implementation of the partition function and the selectionsort function?

I plugged in your functions into a test program I was preparing, and as far as I can tell, your modification of your implementation of quicksort works:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void selectionsort(int *niz, int n) {
    int i;
    for (i = 0; i < n - 1; i++) {
        int j, tmp, maxi = i;
        for (j = i + 1; j < n; j++) {
            if (niz[j] < niz[maxi])
                maxi = j;
        }


        tmp = niz[maxi];
        niz[maxi] = niz[i];
        niz[i] = tmp;
    }
}

int partition(int *niz, int n) {
    int l, r;
    l = 1;
    r = n - 1;
    while (l < r) {
        if (niz[r] >= niz[0]) {
            r--;
        }
        else if (niz[l] < niz[0]) {
            l++;
        }
        else {
            int tmp = niz[l];
            niz[l] = niz[r];
            niz[r] = tmp;
        }
    }
    if (niz[0] < niz[r]) {
        return 0;
    }
    else {
        int tmp = niz[r];
        niz[r] = niz[0];
        niz[0] = tmp;
        return r;
    }
}

void quicksort(int *array, int n) {
    int pi;
    if (n < 2)
        return;
    if (n < 200) {
        selectionsort(array, n);
        return;
    }
    else {
        pi = partition(array, n);
    }
    quicksort(array, pi);
    quicksort(array + pi + 1, n - pi - 1);
}

void populate(int numbers[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        numbers[i] = i;
    }
}

void shuffle(int numbers[], int n) {
    int i;
    int r;
    int temp;
    for (i = n - 1; i > 1; --i) {
        r = rand() % (i + 1);
        if (i != r) {
            temp = numbers[i];
            numbers[i] = numbers[r];
            numbers[r] = temp;
        }
    }
}

int check_sorted(int numbers[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        if (numbers[i] != i) {
            return 0;
        }
    }
    return 1;
}

#define N 1000000

int main(void) {
    int numbers[N];
    srand((unsigned int)time(NULL));
    populate(numbers, N);
    shuffle(numbers, N);
    quicksort(numbers, N);
    printf("Sorted: %d\n", check_sorted(numbers, N));
    return 0;
}

When I comment out the return statement I suggested, it segfaults.

Actually, you can write your modified quicksort a bit more clearly:

Code:

void quicksort(int *array, int n) {
    int pi;
    if (n >= 200) {
        pi = partition(array, n);
        quicksort(array, pi);
        quicksort(array + pi + 1, n - pi - 1);
    }
    else if (n >= 2) {
        selectionsort(array, n);
    }
}