/* Author:
    Sang-bok Lee 2000-11079 (feelyou@kosha.net)
   Desc.:
    header for universal_sorter
*/

#ifndef _universal_sorter_h
#define _universal_sorter_h
// restrict type of elements of data[], and thus range of data[] too,
//     to unsigned long int only
typedef unsigned long int data_type;

// restrict type of the number of elements in data[], and thus index of data[] too,
//     to signed long int only. using unsigned type for index_type will
//     lead to an unexpected outcome because some sort needs -1 index
//     though no actual accessing of data[-1] occurs.
typedef signed long int index_type;

// inline common func. swap()
inline extern void swap(data_type *data1, data_type *data2)
{
    data_type temp;
   
    temp=*data1;
    *data1=*data2;
    *data2=temp;
}

// sorting func.s
extern void insertion_sort(data_type data[], index_type data_num);
extern void merge_sort(data_type data[], index_type left, index_type right);
extern void heap_sort(data_type data[], index_type data_num);
extern void quick_sort(data_type data[], index_type p, index_type r);
extern void quick_sort3(data_type data[], index_type p, index_type r);
extern void counting_sort(data_type data[], index_type data_num, data_type data_range);
extern void radix_sort(data_type data[], index_type data_num);
#endif

/* Author:
    Sang-bok Lee 2000-11079 (feelyou@kosha.net)
   Desc.:
      simple insertion_sort w/ stability
*/

#include "universal_sorter.h"

void insertion_sort(data_type data[], index_type data_num)
{
    // simple insertion_sort(w/ stability)
    // parameters: data_type data[], index_type data_num
    // return: void

    // temp. var.s
    data_type key;
    index_type i,j;

    for(i=1;i<data_num;i++)
    {
        key=data[i];
        for(j=i;data[j-1]>key&&j>0;j--)
            data[j]=data[j-1];
        data[j]=key;
    }
}

/* Author:
    Sang-bok Lee 2000-11079 (feelyou@kosha.net)
   Desc.:
      merge_sort w/ stability
*/

#include "universal_sorter.h"
#include <stdlib.h>    // for malloc(), free()

static void merge(data_type data[], index_type left, index_type mid, index_type right);

void merge_sort(data_type data[], index_type left, index_type right)
{
    // merge_sort
    // parameters: data_type data[], index_type left, right
       //     * right is index of array so it should be (dimension of array)-1
    // return: void

    index_type mid;    // temp. var.

    if(left<right)
    {
        // same as mid=(left+right)/2; but prevents overflow error
        mid=left+((right-left)/2);

        merge_sort(data, left, mid);
        merge_sort(data, mid+1, right);
   
        merge(data, left, mid, right);
    }
}

static void merge(data_type data[], index_type left, index_type mid, index_type right)
{
    // sort and merge 2 subarrays, data[left ~ mid] and data[mid+1 ~ right]
    // into 1 array data[left ~ right] using temp[left ~ right]
    // parameter: data_type data[], index_type left, mid, right
    // return: void

    data_type *temp;    // temp. array
    index_type i,j,k;    // temp. var. for for()

    temp=(data_type *)malloc((right-left+1)*sizeof(data_type));

    i=left;
    j=mid+1;

    for(k=0;i<=mid && j<=right;k++)
    {
        if(data[i]<data[j])
            temp[k]=data[i++];
        else
            temp[k]=data[j++];
    }

    if(i>mid)    // left array(data[left ~ mid]) all used
    {
        for(;j<=right;k++)
            temp[k]=data[j++];
    }
    else        // right array(data[mid+1 ~ right]) all used
    {
        for(;i<=mid;k++)
            temp[k]=data[i++];
    }

    for(i=left;i<=right;i++)
        data[i]=temp[i-left];

    free(temp);
}

/* Author:
    Sang-bok Lee 2000-11079 (feelyou@kosha.net)
   Desc.:
      heap_sort w/o stability
*/

#include "universal_sorter.h"

// macro func.s for common notations
#define LEFT(i) (i*2)+1
#define RIGHT(i) (i*2)+2

static void build_max_heap(data_type data[], index_type data_num);
static void max_heapify(data_type data[], index_type i, index_type heap_size);

void heap_sort(data_type data[], index_type data_num)
{
    // heap_sort
    // parameter: data_type data[], index_type data_num
    // return: void

    index_type i;    // temp. var. for for()
   
    build_max_heap(data, data_num);

    for(i=data_num-1;i>0;i--)
    {
        swap(&data[0], &data[i]);
        max_heapify(data, 0, i);
    }
}

static void build_max_heap(data_type data[], index_type data_num)
{
    // build_max_heap - make a initial max_heap
    // parameters: data_type data[], index_type data_num
    // return: void

    index_type i;

    for(i=data_num/2-1;i>=0;i--)
        max_heapify(data, i, data_num);
}

static void max_heapify(data_type data[], index_type i, index_type heap_size)
{
    // max_heapify - make max_heap from i_th element
    // parameters: data_type data[], index_type i
    // return: void

    // temp. var.s
    index_type largest;
    index_type left, right;

    left=LEFT(i);
    right=RIGHT(i);

    if(left<heap_size && data[left]>data[i])
        largest=left;
    else
        largest=i;

    if(right<heap_size && data[right]>data[largest])
        largest=right;

    if(largest!=i)
    {
        swap(&data[i], &data[largest]);
        max_heapify(data, largest, heap_size);
    }
}

/* Author:
    Sang-bok Lee 2000-11079 (feelyou@kosha.net)
   Desc.:
      simple quick_sort w/o stability
    choosing a pivot w/ the last element.
    (same method as the text but different from the lecture note)
*/

#include "universal_sorter.h"

static index_type partition(data_type data[], index_type p, index_type r);

void quick_sort(data_type data[], index_type p, index_type r)
{
    // quick_sort
    // parameter: data_type data[], index_type p, r
    // return: void

    // temp. var.
    index_type pivot;    // =q in the text & the lecture note
   
    if(p<r)
    {
        pivot=partition(data, p, r);
        quick_sort(data, p, pivot-1);
        quick_sort(data, pivot+1, r);
    }
}

static index_type partition(data_type data[], index_type p, index_type r)
{
    // partition - rerrange the subarray A[p ~ r] in place
    // parameters: data_type data[], index_type p, r
    // return: index of pivot

    index_type i;        // temp. var. for pivot index
    index_type j;        // temp. var. for for()
    data_type pivot_value;    // =q in the text & the lecture note

    pivot_value=data[r];
    i=p;

    for(j=p;j<r;j++)
    {
        if(data[j]<pivot_value)
        {
            swap(&data[i], &data[j]);
            i++;
        }
    }
    swap(&data[i], &data[r]);

    return(i);
}

/* Author:
    Sang-bok Lee 2000-11079 (feelyou@kosha.net)
   Desc.:
      counting_sort w/ stability.
    elements of data[] SHOULD be POSITIVE INTEGERs.
*/

#include "universal_sorter.h"
#include <stdlib.h>    // for malloc(), free()


void counting_sort(data_type data[], index_type data_num, data_type data_range)
{
    // counting_sort
    // parameter: data_type data[], index_type data_num, data_type data_range
    // return: void

    data_type *output;    // =B in the text(output array)
    index_type *temp;    // =C in the text(temp. working storage)

    // assuming that index_type is not smaller than data_type.
    // (a problem may arise when elements of data[] range 0~2000000(long int) but
    //  the number of elements in data[] is just 200(char))
    index_type i;

    data_range++;        // =k in the text(range of integer data)

    output=(data_type *)malloc(data_num*sizeof(data_type));
    temp=(index_type *)malloc(data_range*sizeof(index_type));

    // you can use memset() instead
    for(i=0;i<data_range;i++)
        temp[i]=0;

    // casting is NOT considered
    for(i=0;i<data_num;i++)
        temp[data[i]]++;

    for(i=1;i<data_range;i++)
        temp[i]=temp[i]+temp[i-1];

    // casting is NOT considered
    for(i=data_num-1;i>=0;i--)
        output[--temp[data[i]]]=data[i];

    for(i=0;i<data_num;i++)
        data[i]=output[i];

    free(output);
    free(temp);
}

/* Author:
    Sang-bok Lee 2000-11079 (feelyou@kosha.net)
   Desc.:
      (straight) radix sort w/ stability
    using counting sort code modified to handle bit operation.
    elements of data[] SHOULD be POSITIVE INTEGERs.
*/

#include "universal_sorter.h"
#include <stdlib.h>    // for malloc(), free()

// =d in the text(bit digits of elements of data[]) (1 byte = 8 bits)
#define DATA_DIGITS sizeof(data_type)*8

// sort one quarter of DATA_DIGITS bits at a time(known better than 1 bit-at-a-time)
#define INTERVAL (DATA_DIGITS/4)

// bound of temp. storage(1<<x == 2^x)
#define TEMP_RANGE (1<<INTERVAL)

// inline bit handling func. returning 'digit'th INTERVAL bits from right to left
//     using AND masking technique.
inline static data_type get_interval(data_type x, int digit)
{
    return ( (x>>digit) & ~(~0<<INTERVAL) );
}

void radix_sort(data_type data[], index_type data_num)
{
    // radix_sort using modified counting_sort code
    // parameter: data_type data[], index_type data_num
    // return: void

    data_type *output;    // =B in the text(output array)
    index_type *temp;    // =C in the text(temp. working storage)

    int bit_index;        // temp. var. for outer for()
    index_type i;        // temp. var. for inner for()

    output=(data_type *)malloc(data_num*sizeof(data_type));
    temp=(index_type *)malloc(TEMP_RANGE*sizeof(index_type));

    for(bit_index=0;bit_index<DATA_DIGITS/INTERVAL;bit_index++)
    {
        // you can use memset() instead
        for(i=0;i<TEMP_RANGE;i++)
            temp[i]=0;

        // casting is NOT considered
        for(i=0;i<data_num;i++)
            temp[get_interval(data[i],bit_index*INTERVAL)]++;

        for(i=1;i<TEMP_RANGE;i++)
            temp[i]=temp[i]+temp[i-1];

        // casting is NOT considered
        for(i=data_num-1;i>=0;i--)
            output[--temp[get_interval(data[i],bit_index*INTERVAL)]]=data[i];

        for(i=0;i<data_num;i++)
            data[i]=output[i];
    }

    free(output);
    free(temp);
}

/* Author:
    Sang-bok Lee 2000-11079 (feelyou@kosha.net)
   Desc.:
      improved quick_sort w/o stability
    partitioning using median-of-three method.
*/

#include "universal_sorter.h"

static index_type partition3(data_type data[], index_type p, index_type r);

void quick_sort3(data_type data[], index_type p, index_type r)
{
    // quick_sort3() - same as quick_sort() in quick_sort.c
    // parameter: data_type data[], index_type p, r
    // return: void

    // temp. var.
    index_type pivot;
   
    if(p<r)
    {
        pivot=partition3(data, p, r);
        quick_sort3(data, p, pivot-1);
        quick_sort3(data, pivot+1, r);
    }
}

static index_type partition3(data_type data[], index_type p, index_type r)
{
    // partition -     rerrange the subarray A[p ~ r] in place
    //         using median-of-three method.
    // parameters: data_type data[], index_type p, r
    // return: index of pivot

    index_type i;        // temp. var. for pivot index
    index_type j;        // temp. var. for for()
    index_type mid;        // middle index for median-of-three method
    data_type pivot_value;

    // median-of-three method - sort 3 elements naively.
    mid=(p+r)/2;

    if(data[p]>data[mid])
        swap(&data[p], &data[mid]);
    if(data[p]>data[r])
        swap(&data[p], &data[r]);
    if(data[mid]>data[r])
        swap(&data[mid], &data[r]);

    swap(&data[mid], &data[r-1]);

    pivot_value=data[r-1];
    i=p+1;

    for(j=p+1;j<r-1;j++)
    {
        if(data[j]<pivot_value)
        {
            swap(&data[i], &data[j]);
            i++;
        }
    }
    if(p!=mid)
        swap(&data[i], &data[r-1]);

    return(i);
}