# Thread: How to optimize quicksort with selectionsort

1. ## How to optimize quicksort with selectionsort

I need to modify qsort function.When array length(int n) is,for ex. 200, I need to use selectionsort instead of quicksort.Here is my quicksort implementation.
Code:
```void quicksort(int *array, int n) {
int pi;
if (n < 2)
return;
pi = partition(array, n);
quicksort(array, pi);
quicksort(array + pi + 1, n - pi - 1);
}```

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

3. 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);

}```

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

5. I tried returning but it doesnt work,array is not sorted and some elements are missing.
Code:
```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);

}```

6. 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?

7. Of course it works.
Here is my implementation.
Code:
```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 *niz, int n) {
int pi;
if (n < 2)
return;
pi = partition(niz, n);
quicksort(niz, pi);
quicksort(niz + pi + 1, n - pi - 1);
}```

8. 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);
}
}```

9. Thank you soo much