Quick Sort

Posted on Edited on In Word count in article: 2.1k Reading time ≈ 2 mins.
the simplest quick sort is like following: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>

using namespace std;

int Partition(int * a, int start, int end){
    swap(a[start],a[start+rand()%(end-start+1)]);
    int p = a[start];
    while(start<end){
        while(start<end && a[end] >= p) end--;
        swap(a[start],a[end]);
        while(start<end && a[start]<= p) start++;
        swap(a[start],a[end];)
    }
    return start;
}

void QuickSort(int * a, int start, int end){

     if(end-start>=1){
         int mid = Partition(a,start, end);
         QuickSort(a,start,mid-1);
         QuickSort(a,mid+1,end);
     }
}

But If you want do some optimization in QuickSort, first when the number of elements is small than 10, do insert sort not quick sort. Second, To find the near-like middle element of array, and not use the random one. Third, when the array is already sorted , do not use quick sort. and Reduce the function call. You will the following codes:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>

using namespace std;

void QuickSort(int *a, int start, int end){

    if(end - start <= 0 ) // or you can throw some exceptions!
       return ;

// if the number of element is less than 8, do insert sort;

    if(end - start<7){

      for(int i = start; i <= end; i++){

         for(int j = i; j > start && a[j] < a[j-1]; j--)

             swap(a[j],a[j-1]);

      }

      return;
    }

// check if the array is sorted.

    bool isSorted = true;
    for(int i = start; i < end; i++){
       if(a[i]>a[i+1])
         isSorted = false;
    }
    if(isSorted)
      return;

// get the near-like middle element, use 3 point middle method.

    int dm = start+(end-start)/2;

    int dl, dh;

    if(end-start<40){

       int d = (end-start+1)/8;

       dl = mid(a, start,start+d,start+2*d);

       dm = mid(a,dm-d,dm,dm+d);

       dh = mid(a,end-2*d,end-d, end);

       dm = mid(a,dl,dm,dh);

    }

// do partition

    swap(a[start],a[dm]);

    int low=start, high = end, p = a[start];
    while(low<high){
        while(low < high && a[high]>= p) high--;
        swap(a[low],a[high]);
        while(low<high && a[low]<= p) low ++;
        swap(a[low],a[high]);
    }
    QuickSort(a,start, low-1);
    QuickSort(a,low+1,end);
}