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

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    12

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

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    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.

  3. #3
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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().

  4. #4
    Registered User
    Join Date
    Feb 2012
    Posts
    12
    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?

  5. #5
    Registered User
    Join Date
    Feb 2012
    Posts
    12
    Thank you so much again for your replies.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    > 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.

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.

    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.)

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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:
    Sorting list performances

    There's a ton of examples of this, on the net, even a video or two on YouTube (more humorous perhaps than you want).
    Last edited by Adak; 02-20-2012 at 08:21 PM.

  9. #9
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    > [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?

  10. #10
    Registered User
    Join Date
    Feb 2012
    Posts
    12
    Quote Originally Posted by memcpy View Post
    > [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....

  11. #11
    Registered User
    Join Date
    Feb 2012
    Posts
    12
    Quote Originally Posted by Adak View Post
    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:
    Sorting list performances

    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.....

  12. #12
    Registered User
    Join Date
    Feb 2012
    Posts
    12

    final solution

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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bubble Sort on a Singly Linked List
    By bigmac(rexdale) in forum C++ Programming
    Replies: 9
    Last Post: 03-23-2011, 10:13 AM
  2. sorting a linked list using merge sort question..
    By kakaroto in forum C Programming
    Replies: 17
    Last Post: 08-07-2009, 12:13 PM
  3. Still struggling with sorting a singly linked list
    By jou00jou in forum C Programming
    Replies: 3
    Last Post: 03-13-2008, 11:07 AM
  4. sorting a singly linked list
    By jou00jou in forum C Programming
    Replies: 2
    Last Post: 03-08-2008, 04:22 PM
  5. Quick question on sorting a singly linked list
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 10-08-2001, 11:26 PM

Tags for this Thread