# Quick Sort on a Linked List with a random pivot in C

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

## 评论

### So here is the the solution

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

}
``````

### One problem is with your mer

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

### In case of applying quick so

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