使用隨機數據透視錶快速排序鏈接列表C

Question

我花了很多時間試圖解決這個問題，並在課堂結束。我已經發現了很多有關數組和其他選擇支點的方法，但我只是處於末尾，而且我真的很瘋狂，任何幫助都會讓你無法想象。

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

Answer 1

的一個問題是你的合併代碼 - 它顛倒了less列表，而它前面加上到more名單，這導致垃圾。

Answer 2

因此，對於那些對代碼感興趣的人來說，這是解決問題的方法。我只包含了函數的自我和幫助函數。

乾杯，

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

} 

Answer 3

在應用快速排序的情況下，最好的做法是始終走FLOOR（N/2）爲支點鏈表