Fairly often we have to sort the sequence of objects during solving of problem. I think that Divide and Conquer algorithms are the most effective in solving problem of sortings, here is two of them:
Quick sort algorithm [C++]:
template <typename T>
void quick_sort(T* a, std::size_t begin, std::size_t end) {
std::size_t i = begin, j = end;
T x = a[ (begin+end)/2 ];
do {
while (a[i] < x) ++i;
while (a[j] > x) --j;
if (i <= j) {
if (i < j) { std::swap(a[i], a[j]); }
++i; --j;
}
} while (i <= j);
if (i < end)
quick_sort(a, i, end);
if (begin < j)
quick_sort(a, begin, j);
}
Merge sort algorithm [C++]:
template <typename T>
void merge(T * a, std::size_t begin, std::size_t center, std::size_t end) {
std::size_t i = begin, j = center+1, t = 0;
T* buf = new T[end-begin+1];
while (i <= center && j <= end) {
if (a[i] < a[j])
buf[t++] = a[i++];
else
buf[t++] = a[j++];
}
while (j <= end) buf[t++] = a[j++];
while (i <= center) buf[t++] = a[i++];
for (t = 0; t < end-begin+1; t++)
a[begin+t] = buf[t];
delete [] buf;
}
template <typename T>
void merge_sort(T* a, std::size_t begin, std::size_t end) {
if (begin < end) {
std::size_t split = (begin+end)/2;
merge_sort(a, begin, split);
merge_sort(a, split+1, end);
merge(a, begin, split, end);
}
}
Perfomance:
| quick sort | merge sort
---------|------------|------------
best | O(n log n) | O(n log n)
average | O(n log n) | O(n log n)
worst | O(n^2) | O(n log n)
As you can see in theory quick_sort not so effective beside merge_sort. But some test and measuring of used time, gives:
Merge sort practice tests
1000000 elements 0.24 sec
+ 0.20
2000000 elements 0.44 sec
+ 0.20
3000000 elements 0.64 sec
+ 0.20
4000000 elements 0.84 sec
+ 0.22
5000000 elements 1.06 sec
+ 0.17
6000000 elements 1.23 sec
+ 0.24
7000000 elements 1.47 sec
+ 0.21
8000000 elements 1.68 sec
+ 0.20
9000000 elements 1.88 sec
+ 0.20
10000000 elements 2.08 sec
Quick sort practice tests
1000000 elements 0.19 sec
+ 0.18
2000000 elements 0.37 sec
+ 0.16
3000000 elements 0.53 sec
+ 0.18
4000000 elements 0.71 sec
+ 0.17
5000000 elements 0.88 sec
+ 0.23
6000000 elements 1.11 sec
+ 0.15
7000000 elements 1.26 sec
+ 0.16
8000000 elements 1.42 sec
+ 0.21
9000000 elements 1.63 sec
+ 0.17
10000000 elements 1.80 sec
Here is code of tests, please, share with results of test on your local machine at comments.
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include "sort.hpp"
#define SIZE 10000000
#define START 1000000
#define DIFF 1000000
using namespace std;
/* merge sort testing */
void test_merge_sort() {
printf("\nMerge sort practice tests\n");
uint8_t * a = new uint8_t [SIZE];
for (uint8_t * i = a; i < a+SIZE; ++i)
*i = rand()%256;
float elapsed_time, prev_elapsed_time = 0;
for (size_t size = START; size <= SIZE; size += DIFF) {
clock_t begin = clock();
merge_sort(a, 0, size-1);
clock_t end = clock();
elapsed_time = float(end - begin) / CLOCKS_PER_SEC;
if (prev_elapsed_time != 0)
printf("\t+ %.2f\n", elapsed_time-prev_elapsed_time);
prev_elapsed_time = elapsed_time;
for (uint8_t * i = a; i+1 < a+size; ++i) assert(*i <= *++i);
printf("%d elements %.2f sec\n", size, elapsed_time);
}
}
/* quick sort test */
void test_quick_sort() {
printf("\nQuick sort practice tests\n");
uint8_t * a = new uint8_t [SIZE];
for (uint8_t * i = a; i < a+SIZE; ++i)
*i = rand()%256;
float elapsed_time, prev_elapsed_time = 0;
for (size_t size = START; size <= SIZE; size += DIFF) {
clock_t begin = clock();
quick_sort(a, 0, size-1);
clock_t end = clock();
elapsed_time = float(end - begin) / CLOCKS_PER_SEC;
if (prev_elapsed_time != 0)
printf("\t+ %.2f\n", elapsed_time-prev_elapsed_time);
prev_elapsed_time = elapsed_time;
for (uint8_t * i = a; i+1 < a+size; ++i) assert(*i <= *++i);
printf("%d elements %.2f sec\n", size, elapsed_time);
}
}
int main() {
test_merge_sort();
test_quick_sort();
return 0;
}
AMD FX 8150
Merge sort practice tests 1000000 elements 0.50 sec + 0.45 2000000 elements 0.95 sec + 0.49 3000000 elements 1.44 sec + 0.48 4000000 elements 1.92 sec + 0.50 5000000 elements 2.41 sec + 0.47 6000000 elements 2.89 sec + 0.50 7000000 elements 3.39 sec + 0.45 8000000 elements 3.84 sec + 0.53 9000000 elements 4.37 sec + 0.54 10000000 elements 4.91 sec
Quick sort practice tests 1000000 elements 0.15 sec + 0.15 2000000 elements 0.30 sec + 0.13 3000000 elements 0.43 sec + 0.14 4000000 elements 0.57 sec + 0.15 5000000 elements 0.71 sec + 0.18 6000000 elements 0.89 sec + 0.13 7000000 elements 1.03 sec + 0.13 8000000 elements 1.16 sec + 0.16 9000000 elements 1.32 sec + 0.15 10000000 elements 1.47 sec
Process returned 0 (0x0) execution time : 35.438 s Press any key to continue.