Basic-Sorting-Algorithm

0.1.2.?2. quicksort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
  input: 
          arr:  array for type int *
          low:  index of first element in array
          high: index of last element in arrray
  output:
          arr
  return:
          the last pivotkey index
  prerequisites:
          none 
*/
int partition(int arr[], int low, int high){

    int pivotkey = arr[low];
    int index = 0;
    int temp = 0;

    while(low < high){
        while(low < high && arr[high] >= pivotkey) high--;
        temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;

        while(low < high && arr[low] <= pivotkey) low++;
        temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }
    arr[low] = pivotkey;

    for(index = 0; index <= 5; index++){
        printf("%d\t", arr[index]);
    }
    printf("\n");
    return low;
}

void qsort(int arr[], int low, int high){

    if(low < high){
        int retIndex = partition(arr, low, high);
        qsort(arr, low, retIndex - 1);
        qsort(arr, retIndex + 1, high);
    }
}