/* sort.c : 2007 Oct 12
 * Program to test sort algorithms
 */
 
#include <stdio.h>
#include <stdlib.h>

#define NUM_A            1000

#define DBG_RAND_A        (1<<0)
#define DBG_BUBBLE_SORT   (1<<1)
#define DBG_COCKTAIL_SORT (1<<2)
#define DBG_COMB_SORT     (1<<3)
#define DBG_GNOME_SORT    (1<<4)
#define DBG_HEAP_SORT     (1<<5)
#define DBG_HEAPIFY       (1<<6)
#define DBG_INSERT_SORT   (1<<7)
#define DBG_MERGE_SORT    (1<<8)
#define DBG_QUICK_SORT    (1<<9)
#define DBG_RADIX_SORT    (1<<10)
#define DBG_SELECT_SORT   (1<<11)
#define DBG_SHELL_SORT    (1<<12)
// OR of above:
static int debug = 0;

static int num_swap, num_cmpr;

static char *hex2bin[16] = {
     "0000",  "0001", "0010", "0011", "0100",  "0101", "0110", "0111",
     "1000",  "1001", "1010", "1011", "1100",  "1101", "1110", "1111",
     };
// =====================================================================
void print_a(int num, int *a, char *msg) { int k, h;
    printf("%s =>\nindex : dec   : hex  : bin\n", msg);
    for(k=0; k<num; k++) {
        printf("a[%02d] : %05d : %04X : ", k, a[k], a[k]);
        for(h=12; h>=0; h-=4) 
            printf("%s ", hex2bin[(a[k]>>h)&0xF]);
       printf("\n");
    }
} // print_a
// =====================================================================
int *copy_a(int num, int *a) { int *cpy, k;
    cpy = malloc(sizeof(int)*num);
    for(k=0; k<num; k++) {
        cpy[k] = a[k];
    }
    return cpy;
} // copy_a
// =====================================================================
void *cmpr_a(int num, int *a, int *b, char *srt) { int k;
    for(k=0; k<num; k++) {
        if(a[k] != b[k]) {
            printf("   @@@ cmpr_a difference k=%d for %s (%d,%d)\n",
                k, srt, a[k], b[k]);
            return;
        }
    }
    free(b);
} // cmpr_a
// =====================================================================
void rand_a(int num, int *a) { int k;
// fill a[] with random numebrs in range 0..0xFFFF
    srand(29);
    for(k=0; k<num; k++) {
        a[k] = rand()&0xFFFF;
    }
    if(debug&DBG_RAND_A)
        print_a(num, a, "rand_a");
} // rand_a
// =====================================================================
// swap: a[i] and a[j]
void inline swap(int *a, int i, int j) {
int s;
    s = a[i];
    a[i] = a[j];
    a[j] = s;
    num_swap++;
} // swap
// =====================================================================
int *bubble2_sort(int num, int *a) {
int i, j, *b;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    for(i=0; i<num-1; i++) {
        for(j=i+1; j<num; j++) {
            num_cmpr++;
            if(b[i] > b[j]) { // compare
                swap(b, i, j);
           }
        }
    }
    if(debug&DBG_BUBBLE_SORT)
        print_a(num, b, "bubble2_sort");
    printf("bubble_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // bubble2_sort
// =====================================================================
int *cocktail_sort(int num, int *a) {
int bottom, top, swapped, *b, i;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    bottom = 0;
    top = num-1;
    swapped = 1; 
    while(swapped) { // if no elements have been swapped, then the list is sorted
        swapped = 0; 
        for(i=bottom; i<top; i++) {
            num_cmpr++;
            if(b[i] > b[i + 1]) { // test whether the two elements are in the correct order
                swap(b, i, i+1);
                swapped = 1;
            }
        }
        // decreases `top` because the element with the largest value in the unsorted
        // part of the list is now on the position top 
        top--; 
        for(i=top; i>bottom; i--) {
            num_cmpr++;
            if(b[i] < b[i-1]) {
                swap(b, i, i-1);
                swapped = 1;
            }
        }
        // increases `bottom` because the element with the smallest value in the unsorted 
        // part of the list is now on the position bottom 
        bottom++;  
    }
    if(debug&DBG_COCKTAIL_SORT)
        print_a(num, b, "cocktail_sort");
    printf("cocktail_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // cocktail_sort
// =====================================================================
int *comb_sort(int num, int *a) {
int gap, swapped, *b, i;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    gap = num>>1;
    do {
        swapped = 0;
        //update the gap value for a next comb
        gap *= 10/13;
        if((10==gap) || (9==gap)) {
             gap = 11;
        }
        if(gap < 1)
            gap = 1;
        //a single "comb" over the input list
        for(i=0; i+gap<num; i++) {
            num_cmpr++;
            if(b[i] > b[i+gap]) {
                swap(b, i, i+gap);
                swapped++;
            }
        }
    } while((gap>1) || swapped);
    if(debug&DBG_COMB_SORT)
        print_a(num, b, "comb_sort");
    printf("comb_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // comb_sort
// =====================================================================
int *gnome_sort(int num, int *a) {
int i, j, *b;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    i = 1;
    j = 2;
    while(i < num) {
        num_cmpr++;
        if(b[i-1] <= b[i]) {
            i = j++;
        } else {
            swap(b, i-1, i);
            if(!--i)
                i = 1;
        }
    }
    if(debug&DBG_GNOME_SORT)
        print_a(num, b, "gnome_sort");
    printf("gnome_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // gnome_sort
// =====================================================================
static void heapify(int num, int *a, int root, int bottom) {
int maxc, xtr;
    if(debug&DBG_HEAPIFY)
        printf("heapify(a, num=%d root=%d, bottom=%d)\n", num, root, bottom);
    while(root*2<=bottom) {
        maxc = ((root*2 == bottom) || (a[root*2] >  a[root*2+1])) 
            ? root*2 : root*2+1;
        if(debug&DBG_HEAPIFY)
            printf("maxc=%d\n", maxc);
        if(maxc >= num)
            return;
        num_cmpr++;
        if (a[root] < a[maxc]) {
            swap(a, root, maxc);
            root = maxc;
            if(debug&DBG_HEAPIFY)
                printf("root=%d\n", root);
        } else
            return;
    }
} // heapify

int *heap_sort(int num, int *a) {
int i, *b;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    if(debug&DBG_HEAP_SORT)
        printf("\nheap_sort(num=%d, a)\n", num);
    for(i=(num/2)-1; i>=0; i--)
        heapify(num, b, i, num);
    for(i=num-1; i>=1; i--) {
        swap(b, 0, i);
        heapify(num, b, 0, i-1);
    }
    if(debug&DBG_HEAP_SORT)
        print_a(num, b, "heap_sort");
    printf("heap_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // heap_sort
// =====================================================================
int *insertion_sort(int num, int *a) {
int i, j, v, *b;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    for(i=1; i<num; i++) {
        v = b[i];
        for(j=i; j>0; j--) {
            num_cmpr++;
            if(b[j-1] <= v)
                break;
            num_swap++;
            b[j] = b[j-1];
        }
        b[j] = v;
    }
    printf("insert_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // insertion_sort
// =====================================================================
void merge(int *a, int *t, int left, int mid, int right) {
int i, left_end, num, tmp_pos;
    left_end = mid - 1;
    tmp_pos = left;
    num = right - left;
    while ((left <= left_end) && (mid <= right)) {
        num_cmpr++;
        num_swap++;
        if (a[left] <= a[mid]) {
            t[tmp_pos++] = a[left++];
        } else {
            t[tmp_pos++] = a[mid++];
        }
    }
    while (left <= left_end) {
        num_swap++;
        t[tmp_pos++] = a[left++];
    }
    while (mid <= right) {
        num_swap++;
        t[tmp_pos++] = a[mid++];
    }
    for (i=0; i <= num; i++)  {
        num_swap++;
        a[right] = t[right];
        right--;
    }
} // merge

void m_sort(int num, int *a, int *t, int left, int right) {
int mid;
    if(right > left) {
        mid = (left+right)>>1;
        m_sort(num, a, t, left, mid); // First half
        m_sort(num, a, t, mid+1, right); // Second half
        merge(a, t, left, mid+1, right);
	}
} // m_sort

int *merge_sort(int num, int *a) { int *t, *b;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    t = malloc(sizeof(int)*num);
    m_sort(num, b, t, 0, num-1);
    free(t);
    printf("merge_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // merge_sort
// =====================================================================
int partition(int *a, int left, int right, int pivot) {
int pv, si, i;
    pv = a[pivot];
    swap(a, pivot, right); // Move pivot to end
    si = left-1;
    for(i=left; i<right; i++) {
        num_cmpr++;
        if(a[i] <= pv) {
            si++;
            swap(a, si, i);
        }
    }
    swap(a, right, si+1); // Move pivot to its final place
    return si+1;
} // partition

void q_sort(int *a, int left, int right) {
int pni, pvi;
    if(right > left) {
        // select a pivot index
        //pvi = left;
        pvi = (left+right)>>1;
        pni = partition(a, left, right, pvi);
        q_sort(a, left, pni-1);
        q_sort(a, pni+1, right);
    }
} // q_sort

int *quick_sort(int num, int *a) {
int pni, *b;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    q_sort(b, 0, num-1);
    if(debug&DBG_QUICK_SORT)
        print_a(num, b, "quick_sort");
    printf("quick_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // quick_sort
// =====================================================================
void radix(int num, int byte, int *src, int *dst) {
int count[256], index[256], i;
    for(i=0; i<256; i++)
        count[i] = 0;
    for(i=0; i<num; i++ )
        count[((src[i])>>(byte*8))&0xff]++;
    index[0]=0;
    for(i=1; i<256; i++ )
	    index[i] = index[i-1]+count[i-1];
    for(i=0; i<num; i++ ) {
        num_cmpr++;
        dst[index[((src[i])>>(byte*8))&0xff]++] = src[i];
    }
} // radix

int *radix_sort (int num, int *a) {
// assumes 4 bytes/int
int *b, *t;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    t = malloc(num*sizeof(int));
    radix(num, 0, b, t);
    radix(num, 1, t, b);
    radix(num, 2, b, t);
    radix(num, 3, t, b);
    free(t);
    printf("radix_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    if(debug&DBG_RADIX_SORT)
        print_a(num, b, "radix");
    return b;
} // radix_sort
// =====================================================================
int *selection_sort(int num, int *a) {
// This variant of bubble sort minimizes swaps
int i, j, min, *b;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    for (i=0; i<num-1; i++) {
        min = i;
        for(j=i+1; j<num; j++) {
            num_cmpr++;
            if(b[j] < b[min])        
                min = j;
        }
        if(min != i) // this test is not strictly necessary
            swap(b, i, min);
    }
    if(debug&DBG_SELECT_SORT)
        print_a(num, b, "select");
    printf("select_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // selection_sort
// =====================================================================
int *shell_sort(int num, int *a) {
int i, j, incr, temp, *b;
    num_swap = num_cmpr = 0;
    b = copy_a(num, a);
    incr = num / 2;
    while(incr > 0) {
        for(i=incr; i < num; i++) {
            j = i;
            temp = b[i];
            num_cmpr++;
            while((j >= incr) && (b[j-incr] > temp)) {
                num_swap++;
                b[j] = b[j-incr];
                j -= incr;
            }
            b[j] = temp;
        }
        incr = (2==incr) ? 1 : (int)(incr/2.2);
    }
    if(debug&DBG_SHELL_SORT)
        print_a(num, b, "shell");
    printf("shell_sort num=%d num_swap=%d num_cmpr=%d\n",
        num, num_swap, num_cmpr);
    return b;
} // shell_sort
// =====================================================================
main() {
int a[NUM_A], num=NUM_A, *b, *c;
    rand_a(num, a);
    b = bubble2_sort(num, a);

    c = cocktail_sort(num, a);
    cmpr_a(num, b, c, "cocktail");

    c = comb_sort(num, a);
    cmpr_a(num, b, c, "comb");

    c = gnome_sort(num, a);
    cmpr_a(num, b, c, "gnome");

    c = heap_sort(num, a);
    cmpr_a(num, b, c, "heap");

    c = insertion_sort(num, a);
    cmpr_a(num, b, c, "insert");

    c = merge_sort(num, a);
    cmpr_a(num, b, c, "merge");

    c = quick_sort(num, a);
    cmpr_a(num, b, c, "quick");

    c = radix_sort(num, a);
    cmpr_a(num, b, c, "radix");
    
    c = selection_sort(num, a);
    cmpr_a(num, b, c, "select");

    c = shell_sort(num, a);
    cmpr_a(num, b, c, "shell");

    free(b);
} // main
// =====================================================================