Sorting a singly linked list with quick sort using a random pivot.

I am search high and low for an answer to this what I have thus far works fine using the first element as the pivot element but of course that is not very random..... Any help with this would be so very greatly appreciated.

Code:

---

#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("%lo ", 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)%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, *end, *temp=list->next;


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


    // List Length
    int i=1, j=ListLength(list);


   
    // 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;
        }
        end->next = list;
        list->next = more;


        return less;       
    }
    else
    {
        list->next = more;
       
        return list;   
    }


}


int main(void)
{
    struct listnode *node;


    node = createList(50);


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


    printf("\nSorted List\n");
      Quicksort(node);
    printList(node);
    Brass_test(node);








    exit(0);
}

---

The problem isn't whether the pivot is the first node in your list, it has to do with the value of the pivot node. It just appears to work when the pivot is the first node because the value of the first node is zero, and nothing is smaller that it, thus no less list. Your actual problem is with your separation and merging. The problems I noticed are:

1. You need to initialize temp to list before your Divide & Conq loop, not list->next.
2. You need to make sure to not include the pivot node in your less/more list when you Divide & Conq. Check if (temp == pivot) before adding to less/more.
3. Your merge needs to set end->next to pivot, not list.
4. It also needs to set pivot->next to more, not list->next.
5. It needs to return pivot, not list if less is NULL.

You should remove the pivot from the list, otherwise it will only work for data with no duplicate keys.

You also have to call your quicksort func like this to get the list back:

Code:

---

node = Quicksort(node);

---

You should test it with random data.

And speaking of random, you should call srand(time(0)) as your first executable statement in main (and include time.h) in order to seed the random number generator used by rand().

I am at work I will try once I return home.

1) Yes I need to do that.
2) What if I have more than 1 value that equals the temp?
3) I was lost with this, should I remove a value that equals the pivot from the list so the list is 1 value less, then proceed with the D&Q?
4) This should be obvious with 3
5) Again this follows from previous

Oogabooga

Does the following code not yield somewhat jumbled numbers?

Code:

---

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)%lengthOfList);       (space + i)->next = space + (i+1);     }     (space+(lengthOfList-1))->next = NULL;     node = space;     return node; }

---

Should I call srand(time(0)) in the function I use rand in or just in main?

Thank you so much again for your replies.

> 2) What if I have more than 1 value that equals the temp?
Good question. Do the specs require you to handle duplicates values? The check I suggested checks the address of the pivot, not the value, so you only skip the actual pivot, regardless of whether there are other nodes with the same value. The way you have it coded (the if/else in the D&C loop) will put the duplicate value nodes in the more list, but it should still sort/merge fine.

Yes, you get jumbled numbers with your current code, but it's not random, or even pseudo-random. Your createList function will always produce the same numbers since there's no call to rand() in there. If you notice when you print the list after sorting (when it works), the numbers are all double the index. That is, the sequence is 0, 2, 4, 6, 8, 10, ... in decimal (for some reason you print your list in octal). That is also what the the if (list->value != 2*i) check is for in Brass_test. It would be a good idea to test this with other sets of random data also, so you should have a way to create such a list. You need to call srand() once at the beginning of main. That will make the pseudo-random sequence of numbers generated by rand() different each time you run your program.

Quote:

---

Does the following code not yield somewhat jumbled numbers?

---

Somewhat jumbled is not exactly random. :) The point is that if you test it with such a systematic series of numbers, and only with that series, it may just happen to work for them even though the algorithm is wrong. I assume that's what happened when it seemed to work with always picking the first number.

Quote:

---

The check I suggested checks the address of the pivot, not the value, so you only skip the actual pivot, regardless of whether there are other nodes with the same value.

---

Right. I see. Well that's okay then! (I'm not sure what I was thinking.)

I'm curious WHY you are using Quicksort for sorting a list? It's a poor choice for performance (compared to Merge sort or Bucket sort), and seems anathema to the use of a list, in general.

It seems like you're struggling hard to wear your clothes - upside down and backward. Check out iMalc comments on it, in this thread:
http://cboard.cprogramming.com/c-pro...ml#post1090231

There's a ton of examples of this, on the net, even a video or two on YouTube (more humorous perhaps than you want).

> [C] quicksort.c - Pastebin.com
> sorting - Quick Sort on a Linked List with a random pivot in C - Stack Overflow

Here, pick your duplicate. ¬_¬

So, are you crossposting or copying?

Quote:

---

Originally Posted by memcpy

> [C] quicksort.c - Pastebin.com
> sorting - Quick Sort on a Linked List with a random pivot in C - Stack Overflow

Here, pick your duplicate. ¬_¬

So, are you crossposting or copying?

---

I am cross posting I suppose at this point am quite desperate for help.... But I think with the comments in this thread I will be ok....

Quote:

---

Originally Posted by Adak

I'm curious WHY you are using Quicksort for sorting a list? It's a poor choice for performance (compared to Merge sort or Bucket sort), and seems anathema to the use of a list, in general.

It seems like you're struggling hard to wear your clothes - upside down and backward. Check out iMalc comments on it, in this thread:
http://cboard.cprogramming.com/c-pro...ml#post1090231

There's a ton of examples of this, on the net, even a video or two on YouTube (more humorous perhaps than you want).

---

Annoying assignment from a professor.....

Here is the final solution with the suggestions made in this thread.

Code:

---

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


// 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("%lo ", 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)%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 < 1000000; 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, *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;
        }
        // printf("Temp list %d\n", ListLength(temp));
        // printList(temp);


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


}


int main(void)
{
        // To seend rand()
        srand(time(0));
        struct listnode *node;


        node = createList(1000000);




          node = Quicksort(node);


    Brass_test(node);








        exit(0);
}

---