Quicksort an array in C

Question

I'm trying to sort an array of 10 integers using Quicksort algorithm, this below is my code, it doesn't sort properly, can someone please points me to the possible mistakes i'm doing ?

int partition(int arr[], int first, int last)
{
    int pivot = arr[first];
    int low = first;
    int i = first + 1;
    while(i <= last){
        if(arr[i] < pivot){
            low++;
            swap(&arr[i], &arr[low]);
        }
        i++;
    }
    swap(&arr[first], &arr[low]);
    return low;
}

void quick_sort(int arr[], int first, int last)
{
    int pivot_pos;
    if(first < last){
        pivot_pos = partition(arr, first, last);
        quick_sort(arr, first, pivot_pos-1);
        quick_sort(arr, pivot_pos+1, last);
    }
}

describe your problem clearly. Don't post code and expect people to fix it for you. — ale64bit, Jan 09 '15 at 01:50
You might want to review [Quicksort: Choosing the pivot](http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot/164183#164183), though you might find that a bit to complex as yet (or more complex than you need). What diagnostic printing have you done? Have you checked the values of the partition element and the last and first, etc? You've not shown the code for `swap()`; do you know whether that works correctly? — Jonathan Leffler, Jan 09 '15 at 02:10

score 2 · Answer 1 · answered Jan 09 '15 at 02:38

Here's an instrumented version of your code. Since you didn't provide a swap() function, I wrote that; I also wrote dump_data() to print the contents of a segment of an array, and a main() for testing. On the basis of the limited testing I've done, the sort works. Given that you say it doesn't, I suspect that your swap() code may be faulty; either that or your test harness code is faulty (or my test just happens to be the case that works!).

#include <stdio.h>

static inline void swap(int *a, int *b) { int c = *a; *a = *b; *b = c; }

static void dump_data(const char *tag, int *data, int first, int last)
{
    printf("%s: (%d:%d)\n", tag, first, last);
    for (int i = first; i <= last; i++)
        printf(" %d", data[i]);
    putchar('\n');
}

static
int partition(int arr[], int first, int last)
{
    int pivot = arr[first];
    int low = first;
    int i = first + 1;
    while (i <= last)
    {
        if (arr[i] < pivot)
        {
            low++;
            swap(&arr[i], &arr[low]);
        }
        i++;
    }
    swap(&arr[first], &arr[low]);
    return low;
}

static
void quick_sort(int arr[], int first, int last)
{
    if (first < last)
    {
        dump_data("-->> QS", arr, first, last);
        int pivot_pos = partition(arr, first, last);
        printf("Pivot: arr[%d] = %d\n", pivot_pos, arr[pivot_pos]);
        quick_sort(arr, first, pivot_pos - 1);
        dump_data("-1-- QS", arr, first, pivot_pos - 1);
        quick_sort(arr, pivot_pos + 1, last);
        dump_data("-2-- QS", arr, pivot_pos + 1, last);
        dump_data("<<-- QS", arr, first, last);
    }
}

int main(void)
{
    int data[] = { 9, 2, 4, 7, 1, 3, 8, 6, 5 };
    int size = sizeof(data) / sizeof(data[0]);
    dump_data("Before", data, 0, size - 1);
    quick_sort(data, 0, size - 1);
    dump_data("After", data, 0, size - 1);
    return 0;
}

Example run:

Before: (0:8)
 9 2 4 7 1 3 8 6 5
-->> QS: (0:8)
 9 2 4 7 1 3 8 6 5
Pivot: arr[8] = 9
-->> QS: (0:7)
 5 2 4 7 1 3 8 6
Pivot: arr[4] = 5
-->> QS: (0:3)
 3 2 4 1
Pivot: arr[2] = 3
-->> QS: (0:1)
 1 2
Pivot: arr[0] = 1
-1-- QS: (0:-1)

-2-- QS: (1:1)
 2
<<-- QS: (0:1)
 1 2
-1-- QS: (0:1)
 1 2
-2-- QS: (3:3)
 4
<<-- QS: (0:3)
 1 2 3 4
-1-- QS: (0:3)
 1 2 3 4
-->> QS: (5:7)
 7 8 6
Pivot: arr[6] = 7
-1-- QS: (5:5)
 6
-2-- QS: (7:7)
 8
<<-- QS: (5:7)
 6 7 8
-2-- QS: (5:7)
 6 7 8
<<-- QS: (0:7)
 1 2 3 4 5 6 7 8
-1-- QS: (0:7)
 1 2 3 4 5 6 7 8
-2-- QS: (9:8)

<<-- QS: (0:8)
 1 2 3 4 5 6 7 8 9
After: (0:8)
 1 2 3 4 5 6 7 8 9

More thorough testing would automatically verify that the result is in fact sorted, and also have a larger array with dummy elements that the post-sort checking ensures has not been changed, and would have multiple test runs of different sizes (including 0, 1, 2, 3, 4, and then some larger sizes). This simply tests correctness. To test performance, you do things like test already sorted data, or all values the same, or reverse sorted data, or organ-pipe formations (both ∧ and ∨ form), etc, with and without repeats in the data (as well as random sequences).

Meninx - メネンックス · Accepted Answer · 2015-01-10T13:23:12.487

Based on your code the qsort function is fine even the partition which is a little bit complicated to understand ! I guess your problem is with the swap function ! Here is a working code which uses an easy-to-understand implementation of partition function :

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


/* the aim of the partition is to return the subscript of the exact */
/* position of the pivot when it is sorted */
// the low variable is used to point to the position of the next lowest element
int partition(int arr[], int first, int last)
{
    int pivot = arr[last]; // changed the pivot  
    int low = first;
    int i = first; // changed
    while(i <= last-1 ){// or you can do for(i=first;i<last;i++)
        if(arr[i] < pivot){
            swap(&arr[i], &arr[low]);
            low++; 
        }
        i++;
    }
    swap(&arr[last], &arr[low]);
    // after finishing putting all the lower element than the pivot 
    // It's time to put the pivot into its place and return its position
    return low;
}



void quick_sort(int arr[], int first, int last)
{
    int pivot_pos;
    if(first < last){
        pivot_pos = partition(arr, first, last);
        quick_sort(arr, first, pivot_pos-1);
        quick_sort(arr, pivot_pos+1, last);
    }
}

To test the program you can use the main function below

int main(int argc, char *argv[])
{
    int tab[]={4,53,5,6,7,1};
    quick_sort(tab,0,5);
    int i=0;
    for (i=0;i<6;i++)
    {
        printf(" %d ",tab[i]);
    }
    printf("\n");

    return 0;
}

it will generate the sorted array

1 4 5 6 7 53

If you want to see what happened exactly Here is a complete code :)

#include <stdio.h> 

void affiche(int *p,int size);
void swap(int *p, int a, int b)
{
    int temp=p[a];
        p[a]=p[b];
    p[b]=temp;
}

int partition(int *p, int start, int end)
{
    int pindex=start;
    int pivot=p[end];
    int i=0;
    for (i=start;i<=end-1;i++)
    {
        if (p[i]<pivot)
        {
            printf("swap p[%d] and p[%d]    pivot %d\n",i,pindex,pivot);
            swap(p,i,pindex);
            affiche(p,7);
            pindex++;
        }
    }
            printf("==>swap p[%d] and p[%d]  pivot %d\n",pindex,end,pivot);
    swap(p,pindex,end);
    return pindex;
}
void quicksort(int *p,int a,int b)
{
    if (a<b)
    {
        affiche(p,7);
        int pindex=partition(p,a,b);
        quicksort(p,a,pindex-1);
        quicksort(p,pindex+1,b);
    }
}

void affiche(int *p,int size)
{
int i=0;
for (i=0;i<size;i++)
{
    printf(" %d ",p[i]);
}
printf("\n");

}
int main(int argc, char *argv[])
{
  int tab[]={7,2,4,8,4,0,4};
    affiche(tab,7); 
    quicksort(tab,0,6);
     affiche(tab,7); 

    return 0;
}

Curious: I found that the original partition function worked fine. — Jonathan Leffler, Jan 09 '15 at 06:10
sorry for the late response: yes you are right @JonathanLeffler his code seems working fine ! I guess he has a problem with the swap function ! Moreover, the partition is really hard to understand compared to usual one ! — Meninx - メネンックス, Jan 10 '15 at 13:20

Quicksort an array in C

2 Answers2