Quicksort

An sorting algorithm to sort an array field of integers.

main.cpp
1#include <iostream>
2#include <ctime>
3using namespace std;
4
5void randomize();
6void quickSort(int *, int, int);
7void quicksort(int *, int, int);
8int partition(int *, int, int);
9void hquicksort(int *, int, int);
10int hpartition(int *, int, int);
11void swap(int *, int *);
12void print(int *, int);
13
14int main(int argc, char **argv) {
15    randomize();
16
17    return 0;
18}
19
20void randomize() {
21    int num;
22    cout << "How much numbers do you want to generate?: ";
23    cin >> num;
24    
25    int *field = new int[num];
26    srand(time(0));
27    double time = 0;
28    clock_t start, end;
29    
30    for(int i = 1; i <= num; i++) {
31        field[i] = rand() % 10000;
32    }
33    
34    cout << "Unsorted field of integer numbers:";
35    print(field,num);
36    
37    start = clock();
38    
39    quickSort(field, 0, num);
40    cout << "Sorted field of integer numbers:";
41    print(field,num);
42    end = clock();
43    time = (time + (end - start)) / CLOCKS_PER_SEC;
44    
45    cout << endl << "Ticks: "<< end-start;
46    cout << endl << "Ticks: " << end-start << ':' <<
47CLOCKS_PER_SEC << endl;
48    cout << endl << "Time: " << time << "s" << endl;
49}
50
51//iterative form
52void quickSort(int *field, int lo, int hi) {
53 int i = lo, j = hi, pivot = field[(i+j)/2];
54 int tmp;
55 
56 do {
57  while(field[i] < pivot) i++;
58  while(field[j] > pivot) j--;
59  if(i <= j) {
60   swap(field[i],field[j]);
61   i++;
62   j--; 
63  }
64 } while(i <= j);
65 if(lo < j) quickSort(field, lo, j);
66 if(hi > i) quickSort(field, i, hi);
67}
68
69void swap(int *pos1, int *pos2) {
70    int tmp;
71    tmp = *pos1;
72    *pos1 = *pos2;
73    *pos1 = tmp;
74}
75
76void print(int *field, int n) {
77    int counter = 0;
78    cout << endl << endl;
79    for(int i = 1; i <= n; i++) {
80        counter++;
81        cout << field[i] << ", ";
82        
83        if(counter == 5) {
84            cout << endl;
85            counter = 0;
86        }
87        
88    }
89    cout << endl << endl;
90}
91
92//recursive form
93void quicksort(int *a, int p, int r) {
94    if(p < r) {
95        int q = partition(a, p, r);
96        quicksort(a, p, q-1);
97        quicksort(a, q+1, r);
98    }
99}
100
101int partition(int *a, int p, int r) {
102    int x = a[r]; // pivot
103    int i = p-1;
104    for(int j = p; j < r; j++) {
105        if(a[j] <= x) {
106            i++;
107            swap(&a[i], &a[j]);
108        }
109    }
110    a[r] = a[i+1];
111    a[i+1] = x;
112    return i+1;
113}
114
115// Hoare Partition, see Corman, 3rd edition, page 185
116int hpartition(int *a, int p, int r) {
117    int x = a[p], i = p - 1, j = r;
118    while(1) {
119        do j--; while(a[j] > x);
120        do i++; while(a[i] < x);
121        if(i < j) swap(&a[i], &a[j]);
122        else return j+1;
123    }
124}
125
126// Modification for Hoare Partition, see above
127void hquicksort(int *a, int p, int r) {
128    if(r - p > 1){
129        int q = hpartition(a, p, r);
130        quicksort(a, p, q);
131        quicksort(a, q, r);
132    }
133}