Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <time.h>
- #include <stdio.h>
- #include <stdlib.h>
- #include <memory.h>
- #include <string>
- #include <algorithm>
- using namespace std;
- void sort_bubble(int *a, int n) {
- bool sorted = false;
- while (!sorted) {
- sorted = true;
- for (int i = 0; i < n-1; i++) {
- if (a[i] > a[i+1]) {
- int tmp = a[i];
- a[i] = a[i+1];
- a[i+1] = tmp;
- sorted = false;
- }
- }
- }
- }
- void sort_shaker(int *a, int n) {
- bool sorted = false;
- int l = 0, r = n;
- while (!sorted) {
- sorted = true;
- for (int i = l; i < r-1; i++) {
- if (a[i] > a[i+1]) {
- int tmp = a[i];
- a[i] = a[i+1];
- a[i+1] = tmp;
- sorted = false;
- }
- }
- r--;
- if (sorted) break;
- sorted = true;
- for (int i = r-2; i >= l; i--) {
- if (a[i] > a[i+1]) {
- int tmp = a[i];
- a[i] = a[i+1];
- a[i+1] = tmp;
- sorted = false;
- }
- }
- l++;
- }
- }
- void sort_bubble_traditional(int *a, int n) {
- bool sorted = false;
- for (int i = n-1; --n >- 0;) {
- for (int j = 0; j < i; j++) {
- if (a[j] > a[j+1]) {
- int tmp = a[j];
- a[j] = a[j+1];
- a[j+1] = tmp;
- }
- }
- }
- }
- void sort_insertion(int *a, int n) {
- for (int i = n-1; i > 0; i--) {
- if (a[i-1] > a[i]) {
- int tmp = a[i-1]; a[i-1] = a[i]; a[i] = tmp;
- }
- }
- for (int i = 2; i < n; i++) {
- int j = i;
- int tmp = a[i];
- while (tmp < a[j-1]) {
- a[j] = a[j-1]; j--;
- }
- a[j] = tmp;
- }
- }
- void sort_shell(int *a, int n) {
- int h;
- for (h = 1; h <= n / 9; h = 3*h + 1)
- ;
- for ( ; h > 0; h /= 3) {
- for (int i = h; i < n; i++) {
- int j = i;
- int tmp = a[i];
- while (j >= h && tmp < a[j-h]) {
- a[j] = a[j-h];
- j -= h;
- }
- a[j] = tmp;
- }
- }
- }
- void sort_shell2(int *a, int n) {
- static long long steps[] = {1, 8, 23, 77, 281, 1073, 4193, 16577, 65921, 262913, 1050113, 4197377, 16783361, 67121153, 268460033, 1073790977, 4295065601, 17180065793, 68719869953, 274878693377, 1099513200641, 4398049656833, 17592192335873, 70368756760577};
- int s;
- for (s = 0; steps[s] < n; s++)
- ;
- for (; --s >= 0; ) {
- int h = steps[s];
- for (int i = h; i < n; i++) {
- int j = i;
- int tmp = a[i];
- while (j >= h && tmp < a[j-h]) {
- a[j] = a[j-h];
- j -= h;
- }
- a[j] = tmp;
- }
- }
- }
- void sort_shell3(int *a, int n) {
- int h = n/2;
- for ( ; h > 0; h /= 2) {
- for (int i = h; i < n; i++) {
- int j = i;
- int tmp = a[i];
- while (j >= h && tmp < a[j-h]) {
- a[j] = a[j-h];
- j -= h;
- }
- a[j] = tmp;
- }
- }
- }
- void merge(int *a, int low, int mid, int high, int *aux) {
- int i,j;
- for (i = mid+1; i > low; i--) aux[i-1] = a[i-1];
- for (j = mid; j < high; j++) aux[high+mid-j]=a[j+1];
- for (int k = low; k <= high; k++) {
- if (aux[j] < aux[i])
- a[k] = aux[j--];
- else
- a[k] = aux[i++];
- }
- }
- void mergeSort(int a[], int low, int high, int *aux) {
- const int THRESHOLD = 5;
- if (high - low < THRESHOLD) {
- sort_insertion(a+low, high-low+1);
- } else {
- int mid = (low + high) / 2;
- mergeSort(a, low, mid, aux);
- mergeSort(a, mid+1, high, aux);
- merge(a, low, mid ,high, aux);
- }
- }
- void sort_merge(int *a, int n) {
- int *aux = new int[n];
- mergeSort(a,0,n-1, aux);
- delete [] aux;
- }
- void quickSortBase(int *a, int l, int r) {
- int i = l, j = r;
- int pp[3] = { a[l], a[r], a[(l+r)>>1]};
- if (pp[0] < pp[1]) swap(pp[0],pp[1]);
- if (pp[1] < pp[2]) swap(pp[1],pp[2]);
- if (pp[0] < pp[1]) swap(pp[0],pp[1]);
- int p = pp[1];
- while (i <= j) {
- while (p > a[i])
- i++;
- while (a[j] > p)
- j--;
- if (i <= j) {
- int tmp = a[i];
- a[i] = a[j];
- a[j] = tmp;
- i++;
- j--;
- }
- }
- if (l < j)
- quickSortBase(a, l, j);
- if (i < r)
- quickSortBase(a, i, r);
- }
- void sort_quick_recursive(int *a, int n) {
- quickSortBase(a,0,n-1);
- }
- static void heapify(int *a, int i, int n)
- {
- int curr = a[i];
- int index = i;
- for (;;) {
- int left = index + index + 1;
- int right = left + 1;
- if ( left < n && a[left] > curr)
- index = left;
- if ( right < n && a[right] > a[index])
- index = right;
- if (index == i ) break;
- a[i] = a[index];
- a[index] = curr;
- i = index;
- }
- }
- void sort_heap(int *a, int n) {
- for(int i = n/2-1; i >= 0; i--) {
- heapify(a, i, n);
- }
- while( n > 1 ) {
- n--;
- int tmp = a[0];
- a[0] = a[n];
- a[n] = tmp;
- heapify(a, 0, n);
- }
- }
- void sort_exchange(int *a, int n) {
- for (int i = 0; i < n-1; i++) {
- int imin = i;
- for (int j = i+1; j < n; j++) {
- if (a[j] < a[imin]) imin = j;
- }
- int tmp = a[imin];
- a[imin] = a[i];
- a[i] = tmp;
- }
- }
- void sort_vector(int *a, int n) {
- sort(a+0,a+n);
- }
- int compare_int(const void *a, const void *b) {
- return *(const int *)a - *(const int *)b;
- }
- void sort_qsort(int *a, int n) {
- qsort(a, n, sizeof(int), compare_int);
- }
- typedef void(*sort_func)(int *a, int n);
- struct sort_s {
- sort_func func;
- string name;
- } funcs [] = {
- {sort_bubble, "bubble_simple"},
- {sort_bubble_traditional, "bubble_trad"},
- {sort_shaker, "shaker"},
- {sort_insertion, "insertion"},
- {sort_exchange, "exchange"},
- {sort_shell, "shell"},
- {sort_shell2, "shell2"},
- {sort_shell3, "shell3"},
- {sort_merge, "merge"},
- {sort_heap, "heap"},
- {sort_quick_recursive, "quick recursive"},
- {sort_vector, "vector"},
- {sort_qsort, "qsort"},
- };
- int main(int argc, char **argv) {
- string kind = "random";
- if (argc > 1 && argv[1] == string("random")) {
- kind = "random";
- argc--; argv++;
- }
- if (argc > 1 && argv[1] == string("ascend")) {
- kind = "ascend";
- argc--; argv++;
- }
- if (argc > 1 && argv[1] == string("descend")) {
- kind = "descend";
- argc--; argv++;
- }
- int start_alg = 0;
- if (argc > 1 && argv[1] == string("fastest")) {
- argc--; argv++;
- start_alg = 5;
- }
- int n = 100000;
- if (argc > 1) {
- n = atoi(argv[1]);
- }
- int *copya = new int[n];
- if (kind == "random") {
- srand(time(NULL));
- for (int i = 0; i < n; i++) {
- copya[i] = rand();
- }
- } else if (kind == "ascend") {
- for (int i = 0; i < n; i++) {
- copya[i] = i * 2;
- }
- } else if (kind == "descend") {
- for (int i = 0; i < n; i++) {
- copya[i] = n*2 - i*2;
- }
- }
- int *a = new int[n];
- for (int alg = start_alg; alg < sizeof funcs/sizeof funcs[0]; alg++) {
- memcpy(a, copya, n * sizeof a[0]);
- printf("%30s: ", funcs[alg].name.c_str()); fflush(stdout);
- clock_t start = clock();
- funcs[alg].func(a, n);
- clock_t end = clock();
- printf("%.3f seconds\n", (end - start) / (double)CLOCKS_PER_SEC);
- for (int i = 0; i < n-1; i++) {
- if (a[i] > a[i+1]) {
- printf("sort failed: a[%d]=%d a[%d]=%d\n", i, a[i], i+1, a[i+1]);
- break;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement