Quick Sort on a linked list(Yes I searched)

[fr0st003]

I read through all previous post regarding quicksort on a linked list. The trouble I am having is using a random element, it seems all the other post are using the first or middle element where I want to use a random element for the pivot.

in anycase here is my shot at it.

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

Thanks in advance.

[deceptikon]

So...what's the problem, exactly?

[WaltP]

I read through all previous post regarding quicksort on a linked list. The trouble I am having is using a random element, it seems all the other post are using the first or middle element where I want to use a random element for the pivot.

You may want to, but have you seen any data/algorithm to support that it will work? There may be a reason you found no information about a random pivot element.

Stop looking at posts and look at actual algorithms with explanations. Learn how the sort works. Then you'll know if a random pivot is viable.

[fr0st003]

I understand how it works, are you implying a random pivot w/ a linked list is not possible?

[fr0st003]

From my knowledge and research it is entirely possible for this to work.

[WaltP]

I'm simply implying that if you can find no random pivot information, it may not be possible.

What is the need to use random rather than the normal tried and tested techniques? If just for your own gratification, fine. If you need a sort for some project, use the tested techniques.

[fr0st003]

The following code picks a random element from the list. I didn't find the random element to be the problem.

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

Once I get home from work tonight, I plan to try the follow idea

SelectPivot(random index of list)

list = (list with removed pivot value)

if(list==NULL) return Pivot

partition
less
more

recursive calls
less = quick sort(less)
more = quicksort(more)

if(less!=NULL)
list = less+pivot+more
return list
else
list = pivot + more

I apologize for my pseudo code being garbage but its the best I have.

[fr0st003]

A final solution to the problem.

#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 with some jumbled non random numbers
	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;
		}

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