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