Quick Sort on a Linked List with a random pivot in

Question

I have spent a lot of time trying to work on this problem for a class and am at ends. I have found lots of resources regarding arrays and other ways of selecting a pivot but I am just at ends and am really going crazy here, any help would be so much appreciated you can not possibly imagine.

#include <stdlib.h>     /*and, 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*/
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;
    }



    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);
}

Answer 1

In case of applying quick sort, the best practice is always to take the FLOOR(n/2) As pivot

Answer 2

One problem is with your merge code -- it reverses the less list while prepending it to the more list, which results in garbage.

Answer 3

So here is the the solution to the problem for those that are curious about the code. I included only the function its self and the helper functions.

Cheers,

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

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;
}

// 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, *end, *temp=NULL;

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

    // Remove pivot from list
    while(list !=NULL)
    {
        next = list->next;

        if(list->value != pivot->value)
        {
            list->next=temp;
            temp = list;
        }
        list = next;
    }

    // Divide & Conq
    while(temp != NULL)
    {
        next = temp->next;
        if(temp->value < pivot->value)
        {
            temp->next = less;
            less = temp;
        }
        else 
        {
            temp->next = more;
            more = temp;    
        }
        temp = next;
    }

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

    // Merge
    if(less != NULL)
    {
        end = less;
        while(end->next != NULL){
            end=end->next;
            }
        pivot->next=more;
        end->next = pivot;
        return less;        
    }
    else{
        pivot->next = more;
        return pivot;   
    }

}