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