Subversion Repositories tcp_socket

/* fft.c */

/* Jonathan P Dawson */

/* 2013-12-23 */

/* Based on the in-place algorithm on the Wikipedia page */

/* http://en.wikipedia.org/wiki/Quicksort#In-place_version */

/*globals*/

const unsigned length = 32;

/* partition subarray */

unsigned partition(

        int array[],

        unsigned left,

        unsigned right,

        unsigned pivot_index)

{

    int temp, pivot_value;

    unsigned i, store_index;

    store_index = left;

    pivot_value = array[pivot_index];

    temp = array[pivot_index];

    array[pivot_index] = array[right];

    array[right] = temp;

    for(i=left; i<right; i++){

        if(array[i] <= pivot_value){

            temp = array[store_index];

            array[store_index] = array[i];

            array[i] = temp;

            store_index++;

        }

    }

    temp = array[store_index];

    array[store_index] = array[right];

    array[right] = temp;

    return store_index;

}

/* recursive sort */

void quick_sort(int array[]){

    /* reccursive functions are not supported */

    /* implement a stack explicitly */

    unsigned left, right, pivot;

    unsigned lefts[length];

    unsigned rights[length];

    unsigned stack_pointer = 1;

    /* initialy push whole array onto stack */

    lefts[0] = 0;

    rights[0] = length-1;

    while(stack_pointer){

        /* pop a sub-array from stack */

        stack_pointer--;

        left = lefts[stack_pointer];

        right = rights[stack_pointer];

        /* if the subarray has two or more elements */

        if (left < right){

            /* partition sub array into two further sub arrays */

            pivot = (left + right) >> 1;

            pivot = partition(array, left, right, pivot);

            /* push both subarrays onto stack */

            lefts[stack_pointer] = left;

            rights[stack_pointer] = pivot - 1;

            stack_pointer++;

            lefts[stack_pointer] = pivot + 1;

            rights[stack_pointer] = right;

            stack_pointer++;

        }

    }

}

void main(){

    int array[length];

    unsigned i;

    /* Fill array with zeros */

    for(i=0; i<length; i++){

        array[i] = 0;

    }

    /* Add unsorted data to the array */

    array[0] = 16;

    array[1] = 15;

    array[2] = 14;

    array[3] = 13;

    array[4] = 12;

    array[5] = 11;

    array[6] = 10;

    array[7] = 9;

    array[8] = 8;

    array[9] = 7;

    array[10] = 6;

    array[11] = 5;

    array[12] = 4;

    array[13] = 3;

    array[14] = 2;

    array[15] = 1;

    /* Sort the array */

    quick_sort(array);

    for(i=0; i<length; i++){

        report(array[i]);

    }

}