samedi 24 mars 2018

Randomized Selection Quicksort

I made the randomized selection for quick sort algorithm in C++, and when I use the function in the main it does not do the right sorting. Can someone tell me where I coded wrong please?

I really cannot figure out by myself and I've tried for hours..

Here is my code :

int partition(int a[], int left, int right) {
int pivot = a[right]; int aux;
int i = left - 1;
for (int j = left; j <= right - 1; j++) {
    if (a[j] < pivot) {
        i++;
        aux = a[i];
        a[i] = a[j];
        a[j] = aux;
    }
}
aux = a[i+1];
a[i+1] = a[right];
a[right] = aux;
return (i+1);

}

  int randomized_partition(int a[], int left, int right) {
int aux;
srand(time(NULL));
int i = rand() % right; //(right+1) + left
aux = a[right];
a[right] = a[i];
a[i] = aux;
return partition(a, left, right);

}

 void randomized_quicksort(int a[], int left, int right) {
if (left < right) {
    int pivot = randomized_partition(a, left, right);
    randomized_quicksort(a, left, pivot - 1);
    randomized_quicksort(a, pivot + 1, right);
}

}

int randomized_select(int a[], int left, int right, int i) {
int pivot, k;

if (left == right)
    return a[left];
pivot = randomized_partition(a, left, right);
k = pivot - left + 1;
if (i == k)
    return a[pivot];
else if (i < k)
    return randomized_select(a, left, pivot-1, i);
else if (i > k)
    return randomized_select(a, pivot + 1, right , i - k);

}




Aucun commentaire:

Enregistrer un commentaire