快速排序功能只適用於最後一個值是最大的

Question

我試圖在C中使用快速排序練習。我的程序是一個簡單的結構數組，它接受命令行參數（名稱1年齡1名稱2年齡2 ...等）並以降序輸出所述年齡。

只有最後輸入的年齡最大才能正常工作。除此之外，我得到沒有輸出或Seg Fault 11.有沒有人有任何想法？

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define NameLen 80 
void print_struct(); 

struct people 
{ 
char name [NameLen + 1]; 
int age; 
}; //defining a structure// 

typedef struct people PERSON; 
void quicksort(struct people list[],int,int); 
int main(int argc, const char * argv[]) 

{ 
int i,j; 
j = 0; 
int l = ((argc/2)-1); 


struct people list[l]; //maximum size of array of structs 


    if (argc %2 == 0) //if the number of arguments is an even number 
{ 

printf("Invalid Arguments!\n"); 
printf("Usage : ./hw5 name1 age1 name2 age2 ... "); //print error message and correct program usage 
    exit(0); 
} 

printf("You have entered %d persons(s) into the program \n",(argc/2)); 

for (i=1; i < argc; i+=2) 

{ 
    strcpy(list[j].name, argv[i]); 
    list[j].age = atoi(argv[i+1]); 
    if(list[j].age == 0) 
    { 
     printf("...Invalid age <=0. Try again.\n"); 

     exit(0); 
    } 
    j++; 

} 
    printf("Unsorted Names: \n"); 
    print_struct(&list,argc); 

printf ("Sorted by Age: \n"); 
quicksort(list,0 ,j); 
for(i=0;i<j;i++){ 
    printf("Name : %s| Age : %d\n", list[i].name, list[i].age);}//possible error here? 

//Quicksort Function 

Answer 1

也許問題是j的值。 j是列表的長度嗎？或者列表的長度 - 1？

看起來這會是你想要的東西：列表

printf ("Sorted by Age: \n"); 
quicksort(list,0 ,j-1); 
for(i=0;i<j;i++){ 
    printf("Name : %s| Age : %d\n", list[i].name, list[i].age);} 

Answer 2

的 J =長度的快速排序功能是好的。問題是，你調用一個錯誤：

quicksort(list,0 ,j); 

你傳遞在first和last的值代表了第一個和最後一個元素的索引。從你如何使用j循環遍歷元素可以明顯看出，j是元素的數量。這意味着最後一個元素的索引爲j-1。

所以你傳遞的值是last，它是數組末尾的一個元素。當你嘗試讀/寫這個假元素時，你會調用undefined behavior，在你的情況下（幸運的是）會導致段錯誤。

傳入最後一個元素的實際索引（即一個小於大小）並且它成功運行。

quicksort(list,0 ,j - 1); 

Answer 3

你的循環是不正確的：

while(list[i].age<=list[pivot].age&&i<last) 
     i++; 

這是可能的這個循環與i == last，這是壞的結束，因爲你試圖交換價值，這將是在對陣列的範圍。

while(list[j].age>list[pivot].age) 
     j--; 

這裏，因爲j開始爲last，你開始馬上與讀取陣列之外。

一種可能的解決方法是先向後移動j，然後再測試（do-while樣式）。然後，增量i，測試減量j。

do --j; while(list[j].age>list[pivot].age); 
    do ++i; while(list[i].age<=list[pivot].age&&i<j); 

Answer 4

我讓代碼變得有點簡單（將字符數組更改爲char，使其更簡單）。 我的想法是，當你撥打：

quicksort(list,0 ,j); 

你應該叫的是：

quicksort(list,0 ,j-1); 

因爲最後一個參數必須是數組lenght減1，最後一個位置。

我沒有賽格故障，運行你的代碼，或者我修改了，如果有可能的一個時，仔細檢查您所使用的輸入字符串。

這裏是代碼的「我的」代碼。

希望它有幫助。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define NameLen 80 
void print_struct(); 

struct people 
{ 
    char name; 
    int age; 
}; //defining a structure// 

typedef struct people PERSON; 
void quicksort(struct people list[],int,int); 

int main(int argc, const char * argv[]) 
{ 
    int i,j; 
    j = 10; 
    struct people list[10]; //maximum size of array of structs 

    for (i=0; i < 10; i++) 
    { 
     list[i].name = 'a'; 
     list[i].age = 10-i; 
    } 

    printf("Unsorted Names: \n"); 
    for(i=0;i<j;i++){ 
     printf("Name : %c| Age : %d\n", list[i].name, list[i].age);}//possible error here? 

    printf ("Sorted by Age: \n"); 
    quicksort(list,0 ,j-1); 
    for(i=0;i<j;i++){ 
     printf("Name : %c| Age : %d\n", list[i].name, list[i].age);}//possible error here? 
} 

void quicksort(struct people list[],int first,int last) 
{ 
    struct people temp; 
    int i,j,pivot; 

    if(first<last){ 
     pivot=first; 
     i=first; 
     j=last; 

     while(i<j) 
     { 
      while(list[i].age<=list[pivot].age&&i<last) 
       i++; 
      while(list[j].age>list[pivot].age) 
       j--; 
      if(i<j){ 
       temp=list[i]; 
       list[i]=list[j]; 
       list[j]=temp; 
      } 
     } 

    temp=list[pivot]; 
    list[pivot]=list[j]; 
    list[j]=temp; 
    quicksort(list,first,j-1); 
    quicksort(list,j+1,last); 
    } 
} 

Answer 5

將所有的意見後，這是生成的代碼，這完全編譯，但由於兩名失蹤功能將無法鏈接：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define NAME_LEN (80) 


struct people 
{ 
    char name [NAME_LEN + 1]; 
    int age; 
}; //defining a structure// 

typedef struct people PERSON; 

// print_struct(ptrToList, numElements) 
void print_struct(PERSON *, int); 

// quicksort(ptrToList, firstOffset, numElements) 
void quicksort(struct people list[],int,int); 


int main(int argc, const char * argv[]) 
{ 
    //int i,j; 
    //j = 0; 
    //int l = ((argc/2)-1); 
    int l = argc/2; 

    struct people list[l]; //maximum size of array of structs 

    if (argc %2 == 0) //if the number of arguments is an even number 
    { 
     //printf("Invalid Arguments!\n"); 
     fprintf(stderr, "Invalid Arguments!\n"); 

     //printf("Usage : ./hw5 name1 age1 name2 age2 ... "); //print error message and correct program usage 
     fprintf(stderr, "Usage : %s name1 age1 name2 age2 ... ", argv[0]); 

     // exit(0); 
     exit(EXIT_FAILURE); 
    } 

    //printf("You have entered %d persons(s) into the program \n",(argc/2)); 
    printf("You have entered %d persons(s) into the program \n", l); 

    //for (int i=1; i < argc; i+=2) 
    for (int i=1, j=0; j < l; i+=2, j++) 
    { 
     //strcpy(list[j].name, argv[i]); 
     memset(list[i].name, '\0', NAME_LEN+1); 
     strncpy(list[j].name, argv[i], NAME_LEN); 
     list[j].age = atoi(argv[i+1]); 

     if(list[j].age == 0) 
     { 
      fprintf(stderr, "...Invalid age <=0. Try again.\n"); 

      //exit(0); 
      exit(EXIT_FAILURE); 
     } 
     //j++; 
    } 

    printf("Unsorted Names: \n"); 
    //print_struct(&list,argc); 
    print_struct(list, l); 

    //printf ("Sorted by Age: \n"); 
    //quicksort(list,0 ,j); 
    quicksort(list, 0, l); 

    printf ("Sorted by Age: \n"); 
    // //for(i=0;i<j;i++) 
    //for(int i=0; i<l; i++) 
    //{ 
    // printf("Name : %s| Age : %d\n", list[i].name, list[i].age); 
    //}//possible error here? 
    //} 
    print_struct(list, l); 
} // end function: main 


//Quicksort Function