Hey everyone!
I've been trying to implement a quick sort algorithm for linked list but when i try to run it with 1000000 values my compiler tells me its running too long and ends up not finishing. However when i run it with 10 values it seems to work fine.
Is there anyway to improve this run time?
Code:
struct listnode *quicksort( struct listnode *data ) {
size_t length = 0;
struct listnode *pivNode, *temp = NULL, *low = NULL, *high = NULL, *ltail = NULL, *htail = NULL, *prev = NULL, *end = NULL, *next;
// Get length
for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
length++;
}
// Base case
if( length <= 1 ) { return data; }
// Get and remove pivot from data
pivNode = data;
for( int i = 0; i < rand()%length; i++ ) {
pivNode = pivNode->next;
}
for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
if( cursor == pivNode ) {
if( prev == NULL ){
data = data->next;
}
else {
prev->next = cursor->next;
}
break;
}
else {
prev = cursor;
}
}
// Split into low and high
for( struct listnode *cursor = data; cursor != NULL; cursor = cursor->next ) {
temp = new struct listnode;
temp->value = cursor->value;
temp->next = NULL;
if( cursor->value < pivNode->value ) {
if( ltail == NULL ) {
low = temp;
ltail = temp;
}
else {
ltail->next = temp;
ltail = ltail->next;
}
}
else {
if( htail == NULL ) {
high = temp;
htail = temp;
}
else {
htail->next = temp;
htail = htail->next;
}
}
}
low = quicksort( low );
high = quicksort( high );
if(low != NULL){
pivNode->next = high;
for( struct listnode *cursor = low; cursor != NULL; cursor = cursor->next) {
if( cursor->next == NULL ) {
cursor->next = pivNode;
break;
}
}
return low;
}
else {
pivNode->next = high;
return pivNode;
}