quicksort.c

#include <stdlib.h>     //rand, malloc
#include <stdio.h>      //printf


struct listnode {

    struct listnode *next;
    long value;
};

//Finds length of list, which is usefull in selecting a random pivot
int ListLength (struct listnode *list)
{
    struct listnode *temp = list;

    int i=0;
    while(temp!=NULL)
    {
        i++;
        temp=temp->next;

    }
    return i;
}

// Prints list to help while working on homework
void printList(struct listnode *list)
{
    struct listnode *node;
    node=list;
    printf("\nList Values\n");
    while(node!=NULL)
    {
        printf("%2lo ", node->value);
        node=node->next;
    }
}
// Creates a list of desired length
struct listnode *createList(int lengthOfList)
{
    long i;
    struct listnode *node, *space;
    space =  (struct listnode *) malloc( lengthOfList*sizeof(struct listnode));
    for( i=0; i< lengthOfList; i++ )
    {  (space + i)->value = 2*((17*i+1)%lengthOfList);
       (space + i)->next = space + (i+1);
    }

    (space+(lengthOfList-1))->next = NULL;
    node = space;

    return node;
}

// Prof Brass's test
void Brass_test(struct listnode *list)
{
    int i;
    printf("\nChecking sorted list\n");
    for( i=0; i < 100; i++)
    {
        if( list == NULL )
        {
            printf("List ended early\n"); exit(0);
        }
        if( list->value != 2*i )
        {
            printf("Node contains wrong value\n"); exit(0);
        }
        list = list->next;
   }
   printf("Sort successful\n");
}

// Selects a random pivot point
struct listnode *SelectPivot(struct listnode *list)
{

    int k, n, i = 0;
    n = ListLength(list);


    struct listnode *pivot=list;

    k=rand()%n;

    for (; i < k; ++i)
    {
        pivot=pivot->next;
    }

    return pivot;
}

// Sorts a list using quicksort algo with random pivot point
struct listnode *Quicksort(struct listnode *list)
{
    // Return NULL list
    if (ListLength(list) <= 1) return list;

    struct listnode *less=NULL, *more=NULL, *next, *endl, *temp=list;

    // Select a random pivot point
    struct listnode *pivot = SelectPivot(list);

    printf("Pivot Value = %lo\n", pivot->value);



    // Divide & Conquer
    while(temp != NULL)
    {

        next = temp->next;

        if(temp->value < pivot->value)
        {
            temp->next = less;
            less = temp;
        }
        else
        {
            temp->next = more;
            more = temp;

        }
        temp = next;
    }
    // printf("\nLess list =\n");
    // printf("List Count %d\n", ListLength(less));
    // printList(less);

    // printf("\nMore list =\n");
    // printf("List Count %d\n", ListLength(more));
    // printList(more);


    // printf("\nlist list =\n");
    // printf("List Count %d\n", ListLength(list));
    // printList(list);
    // Recursive Calls


    // less = Quicksort(less);
    // more = Quicksort(more);

    // Merge
    if(ListLength(less)!=0)
    {
        while(endl != NULL)
        {
            endl = less->next;
            less->next = more;
            more = less;
            less = endl;
        }

        return more;
    }
    else
    {


        return more;
    }

}

int main(void)
{
    struct listnode *node;

    node = createList(25);

    printf("Unsorted List\n");
    printList(node);

    printf("\nSorted List\n");
    node =  Quicksort(node);


    printf("\nList Count node %d\n", ListLength(node));
    printList(node);

    // Brass_test(node);




    exit(0);
}
;