An sorting algorithm to sort an array field of integers.
1 | #include <iostream> |
2 | #include <ctime> |
3 | using namespace std; |
4 | |
5 | void randomize(); |
6 | void quickSort(int *, int, int); |
7 | void quicksort(int *, int, int); |
8 | int partition(int *, int, int); |
9 | void hquicksort(int *, int, int); |
10 | int hpartition(int *, int, int); |
11 | void swap(int *, int *); |
12 | void print(int *, int); |
13 | |
14 | int main(int argc, char **argv) { |
15 |     randomize(); |
16 | |
17 |     return 0; |
18 | } |
19 | |
20 | void 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 << ':' << |
47 | CLOCKS_PER_SEC << endl; |
48 |     cout << endl << "Time: " << time << "s" << endl; |
49 | } |
50 | |
51 | //iterative form |
52 | void 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 | |
69 | void swap(int *pos1, int *pos2) { |
70 |     int tmp; |
71 |     tmp = *pos1; |
72 |     *pos1 = *pos2; |
73 |     *pos1 = tmp; |
74 | } |
75 | |
76 | void 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 |
93 | void 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 | |
101 | int 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 |
116 | int 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 |
127 | void 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 | } |