source code

#include "main.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define RAND_RANGE 100

typedef enum {UNSORTED, ACTIVE, PIVOT, SORTED} State;

/* Character to display the state with */
char disp(State s)
{
    if(s==UNSORTED) return ' ';
    if(s==ACTIVE) return '=';
    if(s==PIVOT) return '!';
    if(s==SORTED) return '+';
    return '#';
}

/* Number length (no itoa calling) */
int intlen(int n)
{
    if(n<0) return intlen(-n)+1;
    if(n>9) return intlen(n/10)+1;
    return 1;
}

/* Print array with states */
void print_array(int *a, int _size, State *S)
{
    int i;
    for(i=0;i<_size;i++)
    {
        printf("%i%s ",a[i],(i==_size-1)?"":",");
    }
    printf("\n");
    for(i=0;i<_size;i++)
    {
        printf("%*c  ",intlen(a[i]), disp(S[i]));
    }
}

/* Sorting */
void quicksort_iter(int *a, int size, int left, int right, State *S)
{
    int i;
    int small[right-left+1]; /* arrays for things smaller and larger than the pivot; things equal to the pivot get put in large */
    int large[right-left+1];
    printf("Sorting array of %i elements between indices %i and %i\n",size,left,right);
    for(i=left;i<=right;i++)
    {
        S[i] = ACTIVE;
    }
    if(right<left)
    {
        printf("SOMETHING WENT DESPERATELY WRONG\n");
        exit(-1);
        return;
    }
    if(right==left)
    {
        printf("Nothing to sort\n\n\n");
        S[left] = SORTED;
        print_array(a,size,S);
        getch();
        system("cls");
        return;
    }/* the two bounds are equal and there's nothing to sort */
    if(right==left+1)
    {
        printf("Sorting two elements\n\n\n");
        if(a[left]>a[right])
        {
            int t = a[left];
            a[left]=a[right];
            a[right]=t;
        }
        S[left] = S[right] = SORTED;
        print_array(a,size,S);
        getch();
        system("cls");
        return;
    } /* the two bounds are right next to each other and sorting reduces to a swap */

    /* it's guaranteed past this point that there exists at least one element between a[left] and a[right]
     * or in other words that left+1 < right */

    int pivot = (left+right)/2; /* pick one in the middle */
    int pivot_num = a[pivot]; /* store the pivot number to later put it back in its place */

    int small_count = 0, large_count = 0;

    for(i=left;i<=right;i++)
    {
        if(i!=pivot)
        {
            if(a[i]<pivot_num)
            {
                small[small_count] = a[i];
                small_count++;
            }
            else
            {
                large[large_count] = a[i];
                large_count++;
            }
        }
    }

    /* debug: probing arrays */
    printf("Pivot: %i\n",pivot_num);
    printf("Small array: ");
    for(i=0;i<small_count;i++)
    {
        printf("%i ",small[i]);
    }
    printf("\n");
    printf("Large array: ");
    for(i=0;i<large_count;i++)
    {
        printf("%i ",large[i]);
    }
    printf("\n");

    /* reinserting sorted arrays in place */
    for(i=0;i<small_count;i++)
    {
        a[left+i] = small[i];
    }
    a[left+small_count] = pivot_num;
    for(i=1;i<=large_count;i++)
    {
        a[left+small_count+i] = large[i-1];
    }
    S[left+small_count] = PIVOT;

    /* debug: probing new array */
    print_array(a,size,S);
    getch();
    system("cls");

    S[left+small_count] = SORTED;
    for(i=0;i<small_count;i++)
    {
        S[left+i] = UNSORTED;
    }
    for(i=1;i<=large_count;i++)
    {
        S[left+small_count+i] = UNSORTED;
    }

    if(small_count != 0)
    {
        quicksort_iter(a, size, left, left+small_count-1, S);
    }
    if(large_count != 0)
    {
        quicksort_iter(a, size, left+small_count+1, right, S);
    }
}


int DLL_EXPORT main(void)
{
    int size, i; /* array size & counter, respectively */
    int *a; /* the array to be sorted */
    State *S; /* state array */
    int flag = 1;

    printf("Enter array size: ");
    scanf("%i",&size);
    a = malloc(size * sizeof(int));
    S = malloc(size * sizeof(State));
    for(i=0;i<size;i++)
    {
        S[i] = UNSORTED;
    }

    while(flag)
    {
        printf("Press R to generate a random array; press M to input array manually\n");
        switch(getch())
        {
        case 'r':
        case 'R':
            flag = 0;
            srand(time(NULL));
            for(i=0;i<size;i++)
            {
                a[i] = rand() % (2*RAND_RANGE+1) - RAND_RANGE;
            }
            printf("Randomly generated array: \n");
            for(i=0;i<size;i++)
            {
                printf("%i ",a[i]);
            }
            printf("\n");
            getch();
            system("cls");
            break;
        case 'm':
        case 'M':
            flag = 0;
            printf("Enter array: ");
            for(i=0;i<size;i++)
            {
                scanf("%i",&a[i]);
            }
        }
    }

    quicksort_iter(a, size, 0, size-1, S);

    printf("\n\n\n\nSorted array: ");
    for(i=0;i<size;i++)
    {
        printf("%i ",a[i]);
    }
    printf("\n");
    getchar();
    return 0;
}

extern "C" DLL_EXPORT BOOL APIENTRY DllMain(HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpvReserved)
{
    switch (fdwReason)
    {
        case DLL_PROCESS_ATTACH:
            // attach to process
            // return FALSE to fail DLL load
            break;

        case DLL_PROCESS_DETACH:
            // detach from process
            break;

        case DLL_THREAD_ATTACH:
            // attach to thread
            break;

        case DLL_THREAD_DETACH:
            // detach from thread
            break;
    }
    return TRUE; // succesful
}