20130517 :: Sorting

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef long long ll;
typedef unsigned long long ull;

#define N 1000

#ifdef ASC
    #define less compAsc
#elif DESC_ABS
    #define less compDescAbs
#else
    #error "Use -DASC or -DDESC_ABS to define sorting type"
#endif

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif


ull timestamp(void);
void swap(ll * a, ll * b);
int compAsc(ll a, ll b);
int compDescAbs(ll a, ll b);

ull start, compareCount, swapCount, ticksCount;
ll a[N], tmp[N], heap[N];

ll random() {
    return ((ll)rand() << 49) ^ ((ll)rand() << 32) ^ (rand() << 16) ^ rand();
}

void generateRandom(void) {
    for (int i = 0; i < N; ++i)
        a[i] = random();
}

void generateSorted(void) {
    a[0] = random();
    for (int i = 1; i < N; ++i)
        a[i] = a[i - 1] + rand();
    if (less(1, 0))
        for (int i = 0; i < N; ++i)
            if (rand() & 1) a[i] = -a[i];
}

void reverse(void) {
    int l = 0, r = N - 1;
    while (l < r) swap(a + (l++), a + (r--));
}

void selectionSort(void) {
    int min;
    for (int i = 0; i < N; ++i) {
        min = i;
        for (int j = i + 1; j < N; ++j)
            if (less(a[j], a[min])) min = j;
        swap(a + i, a + min);
    }
}

void heapSort(void) {
    int cur, count = 0;
    for (int i = 0; i < N; ++i) {
        heap[cur = ++count] = a[i];
        while (cur > 1)
            if (less(heap[cur], heap[cur >> 1])) swap(heap + cur, heap + (cur >> 1)), cur >>= 1; else break;
    }
    for (int i = 0; i < N; ++i) {
        a[i] = heap[1], heap[cur = 1] = heap[count--];
        while ((cur << 1) < count) {
            int tmp = cur;
            if (less(heap[cur << 1], heap[tmp])) tmp = cur << 1;
            if (less(heap[(cur << 1) ^ 1], heap[tmp])) tmp = (cur << 1) ^ 1;
            if (tmp == cur) break;
            swap(heap + cur, heap + tmp), cur = tmp;
        }
    }
}

int main() {
    srand(time(NULL));
    printf("\nAlexander Agulenko (c) 2013\n\nNumber of elements in array is %d\n\nSelect type of sequence:\n\t> 1: Elements are in a sorted order\n\t> 2: Elements are in a reversed order\n\t> 3: Elements are in a random order\n\n", N);
    int type;
    scanf("%d", &type);
    if (type == 3) generateRandom(); else {
        generateSorted();
        if (type == 2 && less(0, 1) || type == 1 && less(1, 0)) reverse();
    }
    printf("\nInitial sequence:\n");
    for (int i = 0; i < N; ++i)
        printf(LLD" ", a[i]);
    memcpy(tmp, a, sizeof(a));
    printf("\n\n\n");
    compareCount = swapCount = 0, ticksCount = timestamp(), selectionSort();
    printf("SELECTION SORT\n\nFinal sequence:\n");
    for (int i = 0; i < N; ++i)
        printf(LLD" ", a[i]);
    ticksCount = timestamp() - ticksCount, printf("\n\n> Comparisons count: "LLD"\n> Swaps count: "LLD"\n> CPU ticks count: "LLD"\n\n\n", compareCount, swapCount, ticksCount);
    memcpy(a, tmp, sizeof(tmp));
    compareCount = swapCount = 0, ticksCount = timestamp(), heapSort();
    printf("HEAP SORT\n\nFinal sequence:\n");
    for (int i = 0; i < N; ++i)
        printf(LLD" ", a[i]);
    ticksCount = timestamp() - ticksCount, printf("\n\n> Comparisons count: "LLD"\n> Swaps count: "LLD"\n> CPU ticks count: "LLD"\n\n\n", compareCount, swapCount, ticksCount);
    return 0;
}