Subversion Repositories programming

/* sorts.c - A holder for some common sorts

 *

 * Written By: Ira Snyder

 * Started On: 06-02-2005

 * 

 * License: MIT License

 * License: http://www.opensource.org/licenses/mit-license.php

 *

 * These are all tested and work as long as you give them correct

 * values. DO NOT try giving them a size larger than the array, for example.

 */

#ifndef SORTS_C

#define SORTS_C

#include <stdlib.h> /* for qsort() */

/* include some common functions for dealing with arrays */

#include "arrays.c"

/* ---------- FUNCTION PROTOTYPES ---------- */

/* quicksort -- O(n*logn) best, average. O(n^2) worst */

int cmp_func (const void* _a, const void* _b);

void quicksort (int array[], unsigned long size);

/* mergesort -- O(n*logn) best, average, worst */

void mergesort (int array[], unsigned long size);

void mergesort_rec (int A[], unsigned long min, unsigned long max);

void merge (int A[], unsigned long asize, int B[], unsigned long bsize);

/* insertsort & selectsort -- O(n^2) sorts */

void insertsort (int array[], unsigned long size);

void selectsort(int array[], unsigned long size);

/* swap -- O(1) */

void swap (int *left, int *right);

/* partition -- O(n) way to move an array around a pivot

 *           -- comes from quicksort() (but is not used here) */

int partition (int array[], unsigned long left, unsigned long right);

/* ---------- BEGIN QUICKSORT ---------- */

/* compare function for stdlib's qsort() */

int cmp_func (const void* _a, const void* _b)

{

    const int* a = (const int*) _a;

    const int* b = (const int*) _b;

    if (*a > *b)

        return 1;

    else if (*a == *b)

        return 0;

    else

        return -1;

}

/* wrapper for stdlib's qsort() */

void quicksort (int array[], unsigned long size)

{

    qsort ((void*)array, size, sizeof(int), cmp_func);

}

/* ---------- END QUICKSORT ---------- */

/* ---------- BEGIN MERGESORT ---------- */

/* Mergesort an array

 * Sets up the correct parameters and hands off the work to

 * mergesort_rec()

 * 

 * Complexity: O(n*lgn) */

void mergesort (int array[], unsigned long size)

{

    mergesort_rec (array, 0, size-1);

}

/* The actual mergesort call */

void mergesort_rec (int A[], unsigned long min, unsigned long max)

{

    unsigned long mid = (min+max)/2;

    unsigned long lowerCount = mid - min + 1;

    unsigned long upperCount = max - mid;

    if (max == min)

        return;

    mergesort_rec (A, min, mid);

    mergesort_rec (A, mid+1, max);

    merge (A+min, lowerCount, A+mid+1, upperCount);

}

/* merge two arrays together

 *

 * Complexity: O(n) */

void merge(int A[], unsigned long asize, int B[], unsigned long bsize)

{

    unsigned long ai, bi, ci, i;

    int *C;

    unsigned long csize = asize+bsize;

    C = create_array (csize);

    ai = 0;

    bi = 0;

    ci = 0;

    while ((ai < asize) && (bi < bsize)) 

    {

        if (A[ai] <= B[bi])

        {

            C[ci] = A[ai];

            ci++; ai++;

        }

        else

        {

            C[ci] = B[bi];

            ci++; bi++;

        }

    }

    if (ai >= asize)

        for (i = ci; i < csize; i++, bi++)

            C[i] = B[bi];

        else if (bi >= bsize)

            for (i = ci; i < csize; i++, ai++)

                C[i] = A[ai];

        for (i = 0; i < csize; i++)

            A[i] = C[i];

    C = free_array (C);

}

/* ---------- END MERGESORT ---------- */

/* ---------- BEGIN INSERTION SORT ---------- */

void insertsort (int array[], unsigned long size)

{

    int i, j, v;

    for (i=1; i<size; i++)

    {

        v = array[i];

        j = i;

        while (array[j-1] > v)

        {

            array[j] = array[j-1];

            j--;

            if (j <= 0)

                break;

        }

        array[j] = v;

    }

}

/* ---------- END INSERTION SORT ---------- */

/* ---------- BEGIN SELCTION SORT ---------- */

void selectsort(int array[], unsigned long size)

{

    int i, j, min;

    for (i=0; i<size-1; i++)

    {

        min = i;

        for (j=i+1; j<size; j++)

            if (array[j] < array[min])

                min = j;

        swap (&array[i], &array[min]);

    }

}

/* ---------- END SELECTION SORT ---------- */

/* ---------- BEGIN GENERIC SWAP ---------- */

/* swap two values */

void swap (int *left, int *right)

{

    int temp;

    temp = *left;

    *left = *right;

    *right = temp;

}

/* ---------- END GENERIC SWAP ---------- */

/* ---------- BEGIN PARTITION ---------- */

/* partition from quicksort

 * this partitions an array around the pivot value,

 * which is found in array[left].

 *

 * All values less than the pivot are on the left

 * All values more than the pivot are on the right

 *

 * Complexity: O(n) */

int partition (int array[], unsigned long left, unsigned long right)

{

    unsigned long i, last, pivot;

    pivot = array[left];

    last = left;

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

        if (array[i] < pivot)

        {

           last++;

           swap (&array[last], &array[i]);

        }

    swap (&array[left], &array[last]);

    return last;

}

/* ---------- END PARTITION ---------- */

#endif