1 #include <iostream>
  2 #include "d_timer.h"
  3 #include "d_random.h"
  4 
  5 using namespace std;
  6 
  7 inline void my_swap(int arr[], int i, int j)
  8 {
  9     int temp;
 10     temp = arr[i];
 11     arr[i] = arr[j];
 12     arr[j] = temp;
 13 }
 14 
 15 void bubbleSort(int arr[], int n)
 16 {
 17     int i, j;
 18     bool exchanged = true;
 19     for (i = n - 1; i > 0 && exchanged; --i)
 20     {
 21         exchanged = false;
 22         for (j = 1; j <= i; ++j)
 23             if (arr[j] < arr[j - 1])
 24             {
 25                 my_swap(arr, j, j - 1);
 26 
 27                 exchanged = true;
 28             }
 29     }
 30 }
 31 
 32 void exchangeSort(int arr[], int n)
 33 {
 34     int i, j;
 35     for (i = 0; i < n -1; ++i)
 36         for (j = i + 1; j < n; ++j)
 37             if (arr[j] < arr[i])
 38                 my_swap(arr, j, i);
 39 }
 40 
 41 void selectionSort(int arr[], int n)
 42 {
 43     int i, j;
 44     int min;
 45     for (i = 0; i < n - 1; ++i)
 46     {
 47         min = i;
 48         for (j = i + 1; j < n; ++j)
 49             if (arr[j] < arr[min])
 50                 min = j;
 51         if (min != i)
 52             my_swap(arr, min, i);
 53     }
 54 }
 55 
 56 void insertionSort(int arr[], int n)
 57 {
 58     int i, j;
 59     int temp;
 60     for (i = 1; i < n; ++i)
 61     {
 62         temp = arr[i];
 63         for (j = i; j > 0 && arr[j - 1] > temp; --j)
 64             arr[j] = arr[j - 1];
 65         arr[j] = temp;
 66     }
 67 }
 68 int Sedgewick[17] = { 587521, 260609, 146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1};
 69 void shellSort(int arr[], int n)
 70 {
 71     
 72     int seq;
 73     for (seq = 0; seq < 17; ++seq)
 74     {
 75         if (Sedgewick[seq] < n)
 76             break;
 77     }
 78 
 79     int i, j;
 80     int temp;
 81     for ( ; seq < 17; ++seq)
 82         for (i = Sedgewick[seq]; i < n; ++i)
 83         {
 84             temp = arr[i];
 85             // different from insertion sort e: j >= Sedgewick[seq]
 86             for (j = i; j >= Sedgewick[seq] && arr[j - Sedgewick[seq]] > temp; j -= Sedgewick[seq])
 87                 arr[j] = arr[j - Sedgewick[seq]];
 88             arr[j] = temp;
 89         }
 90 }
 91 
 92 void merge(int arr[], int tmpArr[], int lPos, int rPos, int rEnd)
 93 {
 94     int i, lEnd, num, tmpPos;
 95     lEnd = rPos - 1;
 96     tmpPos = lPos;
 97     num = rEnd - lPos + 1;
 98 
 99     while (lPos <= lEnd && rPos <= rEnd)
100         if (arr[lPos] <= arr[rPos])
101             tmpArr[tmpPos++] = arr[lPos++];
102         else
103             tmpArr[tmpPos++] = arr[rPos++];
104 
105     while (lPos <= lEnd)
106         tmpArr[tmpPos++] = arr[lPos++];
107     while (rPos <= rEnd)
108         tmpArr[tmpPos++] = arr[rPos++];
109 
110     for (i = 0; i < num; i++, rEnd--)
111         arr[rEnd] = tmpArr[rEnd];
112 }
113 void msort(int arr[], int tmpArr[], int left, int right)
114 {
115     int center;
116 
117     if (left < right)
118     {
119         center = (left + right) / 2;
120         msort(arr, tmpArr, left, center);
121         msort(arr, tmpArr, center + 1, right);
122         merge(arr, tmpArr, left, center + 1, right);
123     }
124 }
125 void mergeSort(int arr[], int n)
126 {
127     int *tmpArr;
128 
129     tmpArr = new int[n];
130     if (tmpArr != NULL)
131     {
132         msort(arr, tmpArr, 0, n - 1);
133         delete [] tmpArr;
134     }
135     else
136         cerr << "No space for tmp array!!!" << endl;
137 }
138 
139 inline int leftChild(int i)
140 {
141     return 2 * i + 1;
142 }
143 void percDown(int arr[], int i, int n)
144 {
145     int child;
146     int temp;
147     
148     for (temp = arr[i]; leftChild(i) < n; i = child)
149     {
150         child = leftChild(i);
151         if (child != n - 1 && arr[child + 1] > arr[child])
152             child++;
153         if (temp < arr[child])
154             arr[i] = arr[child];
155         else 
156             break;
157     }
158     arr[i] = temp;
159 }
160 void heapSort(int arr[], int n)
161 {
162     int i;
163     for (i = n / 2; i >= 0; --i)
164         percDown(arr, i, n);
165     for (i = n - 1; i > 0; --i)
166     {
167         my_swap(arr, 0, i);
168         percDown(arr, 0, i);
169     }
170 }
171 
172 int median3(int arr[], int left, int right)
173 {
174     int center = (left + right) / 2;
175 
176     if (arr[left] > arr[center])
177         my_swap(arr, left, center);
178     if (arr[left] > arr[right])
179         my_swap(arr, left, right);
180     if (arr[center] > arr[right])
181         my_swap(arr, center, right);
182     
183     my_swap(arr, center, right - 1);
184     return arr[right - 1];
185 }
186 const int CUTOFF = 30;
187 void QTrueSort(int arr[], int left, int right)
188 {
189     int i, j;
190     int pivot;
191 
192     if (left + CUTOFF <= right)
193     {
194         pivot = median3(arr, left, right);
195         i = left;
196         j = right - 1;
197         for ( ; ; )
198         {
199             while (arr[++i] < pivot) { }
200             while (arr[--j] > pivot) { }
201             if (i < j)
202                 my_swap(arr, i, j);
203             else
204                 break;
205         }
206         my_swap(arr, i, right - 1);
207 
208         QTrueSort(arr, left, i - 1);
209         QTrueSort(arr, i + 1, right);
210     }
211     else
212         insertionSort(arr + left, right - left + 1);
213 }
214 inline void QSort(int arr[], int n)
215 {
216     QTrueSort(arr, 0, n - 1);
217 }
218 
219 
220 int main()
221 {
222     const int SIZE = 10000000;
223     int *arrAscend = new int[SIZE], 
224         *arrDescend = new int[SIZE], 
225         *arrBubble = new int[SIZE], 
226         *arrExchange = new int[SIZE], 
227         *arrSelection = new int[SIZE],
228         *arrInsertion = new int[SIZE], 
229         *arrShell = new int[SIZE], 
230         *arrMergeSort = new int[SIZE], 
231         *arrHeapSort = new int[SIZE],
232         *arrQSort = new int[SIZE];
233     for (int i = 0; i < SIZE; ++i)
234     {
235         arrAscend[i] = i;
236         arrDescend[i] = SIZE - i;
237     }
238     randomNumber rnd;
239     for (int i = 0; i < SIZE; ++i)
240         arrBubble[i] = arrExchange[i] = arrSelection[i] = 
241         arrInsertion[i] = arrShell[i] = arrMergeSort[i] = arrHeapSort[i] = arrQSort[i] = rnd.random(SIZE);
242     timer t;
243 
244     t.start();
245     bubbleSort(arrAscend, SIZE);
246     t.stop();
247     cout << "Bubble Sort Ascend: " << t.time() << endl;
248     t.start();
249     bubbleSort(arrDescend, SIZE);
250     t.stop();
251     cout << "Bubble Sort Descend: " << t.time() << endl;
252     t.start();
253     bubbleSort(arrBubble, SIZE);
254     t.stop();
255     cout << "Bubble Sort Normal: " << t.time() << endl;
256 
257     for (int i = 0; i < SIZE; ++i)
258     {
259         arrDescend[i] = SIZE - i;
260     }
261     t.start();
262     exchangeSort(arrAscend, SIZE);
263     t.stop();
264     cout << "Exchange Sort Ascend: " << t.time() << endl;
265     t.start();
266     exchangeSort(arrDescend, SIZE);
267     t.stop();
268     cout << "Exchange Sort Descend: " << t.time() << endl;
269     t.start();
270     exchangeSort(arrExchange, SIZE);
271     t.stop();
272     cout << "Exchange Sort Normal: " << t.time() << endl;
273 
274     for (int i = 0; i < SIZE; ++i)
275     {
276         arrDescend[i] = SIZE - i;
277     }
278     t.start();
279     selectionSort(arrAscend, SIZE);
280     t.stop();
281     cout << "Selection Sort Ascend: " << t.time() << endl;
282     t.start();
283     selectionSort(arrDescend, SIZE);
284     t.stop();
285     cout << "Selection Sort Descend: " << t.time() << endl;
286     t.start();
287     selectionSort(arrSelection, SIZE);
288     t.stop();
289     cout << "Selection Sort Normal: " << t.time() << endl;
290 
291     for (int i = 0; i < SIZE; ++i)
292     {
293         arrDescend[i] = SIZE - i;
294     }
295     t.start();
296     insertionSort(arrAscend, SIZE);
297     t.stop();
298     cout << "Insertion Sort Ascend: " << t.time() << endl;
299     t.start();
300     insertionSort(arrDescend, SIZE);
301     t.stop();
302     cout << "Insertion Sort Descend: " << t.time() << endl;
303     t.start();
304     insertionSort(arrInsertion, SIZE);
305     t.stop();
306     cout << "Insertion Sort Normal: " << t.time() << endl;
307 
308     for (int i = 0; i < SIZE; ++i)
309     {
310         arrDescend[i] = SIZE - i;
311     }
312     t.start();
313     shellSort(arrAscend, SIZE);
314     t.stop();
315     cout << "Shell Sort Ascend: " << t.time() << endl;
316     t.start();
317     shellSort(arrDescend, SIZE);
318     t.stop();
319     cout << "Shell Sort Descend: " << t.time() << endl;
320     t.start();
321     shellSort(arrShell, SIZE);
322     t.stop();
323     cout << "Shell Sort Normal: " << t.time() << endl;
324 
325     for (int i = 0; i < SIZE; ++i)
326     {
327         arrDescend[i] = SIZE - i;
328     }
329     t.start();
330     mergeSort(arrAscend, SIZE);
331     t.stop();
332     cout << "MergeSort Ascend: " << t.time() << endl;
333     t.start();
334     mergeSort(arrDescend, SIZE);
335     t.stop();
336     cout << "Merge Sort Descend: " << t.time() << endl;
337     t.start();
338     mergeSort(arrMergeSort, SIZE);
339     t.stop();
340     cout << "Merge Sort Normal: " << t.time() << endl;
341 
342     for (int i = 0; i < SIZE; ++i)
343     {
344         arrDescend[i] = SIZE - i;
345     }
346     t.start();
347     heapSort(arrAscend, SIZE);
348     t.stop();
349     cout << "Heap Sort Ascend: " << t.time() << endl;
350     t.start();
351     heapSort(arrDescend, SIZE);
352     t.stop();
353     cout << "Heap Sort Descend: " << t.time() << endl;
354     t.start();
355     heapSort(arrHeapSort, SIZE);
356     t.stop();
357     cout << "Heap Sort Normal: " << t.time() << endl;
358 
359     for (int i = 0; i < SIZE; ++i)
360     {
361         arrDescend[i] = SIZE - i;
362     }
363     t.start();
364     QSort(arrAscend, SIZE);
365     t.stop();
366     cout << "Quick Sort Ascend: " << t.time() << endl;
367     t.start();
368     QSort(arrDescend, SIZE);
369     t.stop();
370     cout << "Quick Sort Descend: " << t.time() << endl;
371     t.start();
372     QSort(arrQSort, SIZE);
373     t.stop();
374     cout << "Quick Sort Normal: " << t.time() << endl;
375 
376     delete [] arrAscend;
377     delete [] arrDescend;
378     delete [] arrBubble; 
379     delete [] arrExchange;
380     delete [] arrSelection;
381     delete [] arrInsertion; 
382     delete [] arrShell;
383     delete [] arrMergeSort;
384     delete [] arrHeapSort;
385     delete [] arrQSort;
386     return 0;
387 }