CODEWITHSUNDEEP
csortingdata-structuresquicksort
Ayesha Shakeel
Ayesha Shakeel

Reputation: 1

What's wrong with this Quick Sort program?

I am sort of a beginner at coding and this is my C program for quick sort. Something seems to be wrong though because for the array {6,76,32,18,9,90,43,45,3,1} the output comes out as {1,3,6,9,18,32,45,43,76,90}. I don't know why 45 is coming before 43?

#include <stdio.h>

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

int partition(int list[], int l, int r) {
    int pi = l;
    int too_big = l + 1;
    int too_small = r;

    while (too_big < too_small) {
        while (list[too_big] <= list[pi] && too_big < r)
            too_big++;
        while (list[too_small] > list[pi] && too_small > l)
            too_small--;
        if (too_big < too_small)
            swap(&list[too_big], &list[too_small]);
    }
    swap(&list[pi], &list[too_small]);

    return too_small;
}

void qsort(int list[], int l, int r) {
    if (l < r) {
        int pi = partition(list, l, r);
        qsort(list, l, pi - 1);
        qsort(list, pi + 1, r);
    }
}

Upvotes: 0

Views: 102

Answers (1)

M Oehm
M Oehm

Reputation: 29126

You can debug your function by printing the partitioned array before returning from partition. For your example, you get:

  3  1  6 18  9 90 43 45 32 76
       ^^
  1  3  .  .  .  .  .  .  .  .
    ^^
  .  .  .  9 18 90 43 45 32 76
             ^^
  .  .  .  .  . 76 43 45 32 90
                            ^^
  .  .  .  .  . 32 43 45 76  .
                         ^^
  .  .  .  .  . 32 43 45  .  .
                ^^
  .  .  .  .  .  . 45 43  .  .
                      ^^

(^^ marks the pivot.) You'll see that 45 and 43 are swapped, but they shouldn't, because they are already in order.

The faulty swap happens when you swap the pivot into place unconditionally at the end and when you are partitioning an array of two elements. In that case, the main loop isn't entered and you may have too_small sitting on an element that doesn't belong to the left partition.

Check whether swapping disturbs the partition before swapping.

Upvotes: 5

Related Questions