implement Quicksort in C

Question

What I want to do is quick-sort this 12 integer datas {2,3,11,9,12,2,6,15,18,10,7,14}.

And I should select the pivot 14 which is located in index-11.

The env. of practice is GCC.

#include <stdio.h>
#include <stdlib.h>
#define DATA_SIZE 12
void quick_sort(int *list, int left, int right);
int partition(int *list, int left, int right);
void SWAP(int *x, int *y, int *t) { *t = *x; *x = *y; *y = *t; }
/*main start*/
int main() {
    //Initialize data[] for sorting
    int data[DATA_SIZE] = {2,3,11,9,12,2,6,15,18,10,7,14};
    quick_sort(data, 0, DATA_SIZE-1);
    for(int i = 0; i < DATA_SIZE; i++) { printf("%d\t",data[i]);}
    return 0;
}

/*Main fuction for recursion.*/
void quick_sort(int *list, int left, int right) {
    if(left < right) {
        //Pivot selection
        int q = partition(list, left, right);
        //Divide
        quick_sort(list, left, q-1);
        quick_sort(list, q+1, right);
    }
}

/*Devide and Conquere*/
int partition(int *list, int left, int right) {
    int pivot;              //pivot
    int temp;               //temporary variable
    int low;                
    int high;               

    // select 
    low = left;
    high = right+1;
    pivot = list[11];

    do {
        //proceed
        do low++; while(list[low]<pivot);
        do high--; while(list[high]>pivot);
        //pivot-comparison
        if(low < high) SWAP(&list[low],&list[high], &temp);
    }while(low < high);
    //swap after comparison
    SWAP(&list[left], &list[high], &temp);
    return high;
}

the result is in below.

3 6 2 7 10 9 11 12 14 2 15 18

As result is awkward, so I inserted printf("pivot : %d\n", pivot); in the partition().

pivot : 14
pivot : 7
pivot : 6
pivot : 3
pivot : 11
pivot : 9
pivot : 15

So I fixed the code high = right+1; in the partition() to high = right.

pivot : 14
pivot : 14
pivot : 14
pivot : 14
pivot : 14
pivot : 14
pivot : 14
pivot : 14
pivot : 14

but the sort result is

11 3 12 9 6 2 10 7 18 15 2 14

You might want to do some more research about [how to choose pivot](https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot). Especially in regards to *hard-coding* it. — Some programmer dude, Apr 12 '18 at 05:51
@Someprogrammerdude That may affect performance, not the end result. — CinCout, Apr 12 '18 at 05:52
@Someprogrammerdude Yes, I know the importance of pivot selection, but I just wanted to try the fixed-pivot. thanks. — robin eu, Apr 12 '18 at 05:53
I also suggest you [learn how to debug your programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/), especially learn how to use a *debugger* to step through the code line by line. Doing that, while monitoring all variables, should help in finding and solving problems like this. — Some programmer dude, Apr 12 '18 at 05:56
@Someprogrammerdude I use *GCC* compiler, Could I ask about how to use debugger of GCC ? or just url link. — robin eu, Apr 12 '18 at 05:57

score 2 · Answer 1 · answered Apr 12 '18 at 05:52

2

Your approach is wrong: You don't define a pivot but you define an algorithm that selects a pivot. Examples for algorithms are

Pick the first element.
Pick an element in the middle.
Pick a random element.

The last one is practically the most important one. However, for training purposes, use the first one. The point is that using a deterministic behaviour makes it easier to debug. The random pivot can come later, in the spirit of "Devide and Conquer".

answered Apr 12 '18 at 05:52

Ulrich Eckhardt

16,572
3
28
55

You can find [Quicksort: Choosing the Pivot](https://stackoverflow.com/questions/164163/) for some other options. For big enough data sets, some implementations use a median of three medians of three. – Jonathan Leffler Apr 12 '18 at 05:56
Maybe Can I reverse the values of `data[]`? – robin eu Apr 12 '18 at 05:56
I don't understand your question, @robineu. – Ulrich Eckhardt Apr 12 '18 at 05:57
`{2,3,11,9,12,2,6,15,18,10,7,14}` to `{14,7,10,18,15,6,2,12,9,11,3,2}` @UlrichEckhardt – robin eu Apr 12 '18 at 06:00
You can also delete your data altogether, an empty sequence is always properly sorted. Sorry, it's still not clear what you want to know. Anyhow, here's an advise: Try it! If it fails and you don't understand why, use a debugger to step through to gain that understanding. – Ulrich Eckhardt Apr 12 '18 at 06:02

score 2 · Answer 2 · answered Apr 12 '18 at 05:55

2

pivot = list[11];

And I should select the pivot 14 which is located in index-11.

No, it is not index 11. It's the right-most element of each sub list, not some hard coded index. By choosing an invalid pivot element, partitioning stops working.

answered Apr 12 '18 at 05:55

Ext3h

5,713
17
43

implement Quicksort in C

2 Answers2