CODEWITHSUNDEEP
csorting
pp182
pp182

Reputation: 107

What's wrong with this quicksort program that I adapted?

edit: added main function

int main(int argc, char *argv[]) {
    int arr[] = {3, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);

    quicksort(arr, 0, n-1);
    for (int i=0; i<n; i++) {
        printf("%3d", arr[i]);
    }

    return 0;
}

void quicksort(int arr[], int left, int right) {
    if (left<right) {
        int pivot = partition(arr, left, right);
        quicksort(arr, left, pivot-1);
        quicksort(arr, pivot+1, right);
    }
}

int partition(int arr[], int left, int right) {
    /* left to i = smaller than pivot
    i+1 = pivot
    i+2 to right = bigger than pivot */
    int pivot = right, i = left-1;
    for (int j=left; j<right-1; j++) { // right-1 because the last num is the pivot
        if (arr[j] < arr[pivot]) {
            /* j scans the array for values that need to be swapped into the
            right side of the partition */
            i++;
            swap(&arr[j], &arr[i]);
        }
        // swap pivot into the middle
        swap(&arr[i+1], &arr[right]);
    }
    return i+1; // index of pivot
}

void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

I was following a tutorial and tried to translate pseudocode into C but I'm not sure what's wrong with my code

I'm using the input 3,2,1 but its outputting 2 1 3

Upvotes: 1

Views: 51

Answers (1)

LZR
LZR

Reputation: 958

int partition(int arr[], int left, int right) {
    int pivot = right;
    int i = left; // <-- set I to left not left -1
    for (int j=left; j<right; j++) { // <-- no need for -1 (you already use less and not less or equal operator
        if (arr[j] < arr[pivot]) {
            swap(&arr[j], &arr[i]); // <-- do the swap first, then increment
            i++;
        }
    }

    // swap pivot into the middle
    swap(&arr[i], &arr[right]); // <-- this needs to be outside the loop

    return i; // <-- return I not I + 1
}

Upvotes: 1

Related Questions