in Quick Sort. and this is C

 int number = 10;

    int[]  data = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

    void show() {
        int i;
        for(i = 0; i < number; i  ) {
            printf("%d ", data[i])
        }
    }

    void quickSort(int* data, int start, int end){
        if (start >= end){ // privent if there is only one parameter
            return;
        }

    int key = start; //key is first index in data[], key is pivot.
    int i = start   1, j = end, temp;

    while(i <= j) { //repeat upto i has big index value than j
        while(i <= end && data[i] <= data[key]) { i   } // upto i reach to bigger value than key in data[]
        while(j > start && data[j] >= data[key]) { j-- } //upto j reach to smaller value than key in data[]
    }

    if( i > j) { // exchange i and j if i is bigger than j
        temp = data[j];
        data[j] = data[key];
        data[key] = temp;
    } else {
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    //recursive function
    quickSort(data, start, j - 1);
    quickSort(data, j   1, end);
}

int main(void) {
    quickSort(data, 0, number - 1);
    show();
    return 0;
}

I'm not sure you understand what I want to ask you... I'm sorry, anyways if you don't understand what that code is, please visit this address(https://www.geeksforgeeks.org/cpp-program-for-quicksort/) probably you can get what I wrote.

here's the thing. in Quick Sort //recursive function quickSort(data, start, j - 1); quickSort(data, j 1, end); this part, start is going to be 0. then key(pivot) will be data[0] and I expect data[key] is always be data[0] because there is no mention about key. so I think in this case data[key] should be 1 everytime. but the result is not like that. in quick sort, {1, 10, 5, 8, 7, 6, 4, 3, 2, 9} here, pivot is 1. then data[i] is 10 and data[j] is 9. according to the code 1 is fixed and next pivot will be 10. yes. why? why the next pivot will be 10? there is no mention about pivot!!!!

Do you know why the pivot is chage to next index even though there is no mention about it? if you understand please let me know... I'm so sorry about this kind of dirty grammer and expression.... p.s. I'm student.... :(

CodePudding user response：

Quicksort work in a way that it is recursive.

1. takes pivot (any number in list, first in your example)
2. reorder list in a way, that numbers <= pivot are in lower part and > pivot are upper part. (while loop)
3. quicksort lower and quicksort upper part. (2 recursive quicksort calls)

Now since your fist pivot is 1. Than there is no number that is <= pivot and lower part is empty and first quicksort gets terminated at first return at beginning of call.

Quicksort for upper call is then called in a way that first number (start) point to beginning of upper part (start is 1 and points to number 10) and end similarly point to last index of array.

I hope it makes sense.

CodePudding user response：

I'm not exactly very good with words, but these video resources below have a nice visualisation for the quick sort algorithm and the pivot, and how it is used during the quick sorting.

AFAIK, the Pivot is a random element selected from the pool of elements, so that you can compare and start ordering the group of elements. Since this a recursive algorithm, for each new run you will need to choose a new pivot (example for comparison), so that you can sort the elements after or before the pivot. The pivot is just comparison element, so that you can get it and say: this is larger than (or not) than my current element.

Those vids helped me to better understand what is happening with the elements.

https://youtu.be/vxENKlcs2Tw?t=66
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://www.youtube.com/watch?v=MZaf_9IZCrc