알파벳 순서로 연결된 목록을 C로 정렬하는 방법

Question

링크 된 목록을 사전 순으로 정렬하려고하지만 내 정렬 알고리즘처럼 보이지 않습니다. 내 목록을 어떻게 정렬합니까?

Answer 1

코드를 한 번 더보고 나서 @TenTen Peter의 원래 의도와 일치하도록 최적화했습니다. 외부 루프는 필요하지 않습니다. 정렬이 제대로 수행됩니다

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

// definition of the structure (global scope) 
typedef struct s_file 
{ 
    char  *file_name; 
    struct  s_file *next; 
} t_file; 

int static counter = 0; 

void sort_alpha(t_file **begin_list) 
{ 
    t_file *list; 
    char *tmp; 
    list = *begin_list; 
    if (list) 
    { 
     while (list && list->next) 
     { 
      if (strcmp(list->file_name, list->next->file_name) > 0) 
      { 
       tmp = list->file_name; 
       list->file_name = list->next->file_name; 
       list->next->file_name = tmp; 
       counter = counter + 1; 
       printf("swap=%d\n",counter); 
      } 
     list = list->next; 
     } 
    } 
} 

int list_size(t_file **alst) 
{ 
    int size = 0; 
    t_file *conductor; // This will point to each node as it traverses the list 
    conductor = *alst;  
    if (conductor != 0) 
    { 
     size = 1; 
     while (conductor->next != 0) 
     { 
      conductor = conductor->next; 
      size = size + 1; 
     } 
    } 
    return size; 
} 

void list_add(t_file **alst, t_file *newElement) 
{ 
    printf("list_add->"); 
    if (newElement) 
    { 
     newElement->next = *alst; 
     *alst = newElement; 

     // Printing the added element 
     printf("list_add:newElement=%s\n",(*alst)->file_name); 

     // sorting: 
     sort_alpha(alst); 
    } 
    else 
    { 
     printf("NULL entry\n"); 
    } 
} 

t_file *newEntry(char *file_name) 
{ 
    t_file *file; 
    file = (t_file *) malloc(sizeof(t_file)); 
    printf("newEntry:file_name= %s\n",file_name); 
    if (file) 
    { 
     file->file_name = file_name; 
     file->next = NULL; 
    } 
    return (file); 
} 

// Untested 
void read_dir(char *dir_name, t_file **begin_list) 
{ 
    DIR *dir; 
    struct dirent *entry; 
    dir = opendir(dir_name); 
    if (!dir) 
    { 
     perror(dir_name); 
     return; 
    } 
    while ((entry = readdir(dir)) != NULL){ 
     list_add(begin_list, newEntry(entry->d_name)); 
    }  
    closedir(dir); 
} 

int main(int ac, char **av) 
{ 
    t_file *s,*iter,*e2,*e3,*e4,*e5,*e6,*e7; 
    int j=0; 

    printf("*Program Start*\n");   

    // Creating entries: 
    s = newEntry("dHea"); 
    e2 = newEntry("bbcx"); 
    e3 = newEntry("abcd"); 
    e4 = newEntry("cbcd"); 
    e5 = newEntry("cbad"); 
    e6 = newEntry("bbcd"); 
    e7 = newEntry("cbaa"); 

    // Adding entries to the list and sorting at the same time 
    list_add(&s, e2); 
    list_add(&s, e3); 
    list_add(&s, e4); 
    list_add(&s, e5); 
    list_add(&s, e6); 
    list_add(&s, e7); 

    // It was done by: 
    // read_dir(av[1], &s); // Untested 

    // Print the sorted list 
    iter = s; 
    while (iter) 
    { 
     j++; 
     printf("Printing sorted list: element %d = %s\n",j,iter->file_name); 
     iter = iter->next; 
    } 

    printf("*Program End**\n"); 
    return 0; 
} 

출력 :

*Program Start* 
newEntry:file_name= dHea 
newEntry:file_name= bbcx 
newEntry:file_name= abcd 
newEntry:file_name= cbcd 
newEntry:file_name= cbad 
newEntry:file_name= bbcd 
newEntry:file_name= cbaa 
list_add->list_add:newElement=bbcx 
list_add->list_add:newElement=abcd 
list_add->list_add:newElement=cbcd 
swap=1 
swap=2 
list_add->list_add:newElement=cbad 
swap=3 
swap=4 
list_add->list_add:newElement=bbcd 
swap=5 
list_add->list_add:newElement=cbaa 
swap=6 
swap=7 
swap=8 
Printing sorted list: element 1 = abcd 
Printing sorted list: element 2 = bbcd 
Printing sorted list: element 3 = bbcx 
Printing sorted list: element 4 = cbaa 
Printing sorted list: element 5 = cbad 
Printing sorted list: element 6 = cbcd 
Printing sorted list: element 7 = dHea 
*Program End** 

코드는 여기에 있습니다 : code

편집 : 하나 내가 스왑 카운터를 추가 한 위의 알고리즘의 효율성에 대한 우려가있을 수 있기 때문에. 그것은 포인터를 교환해야 할 필요가 몇 번 있었는지 계산합니다. (복사가 필요 없음). 위의 데이터의 알고리즘은 매우 효율적으로 보입니다. 우리의 7 가지 요소 목록에서 8 가지 스왑 만!

다양한 소팅 알고리즘이 분류되는 시간을 비교하는 :

버블 정렬 [기기 : O (N), 최악 : O (N^2)]

선택 정렬 [최고/최악 : O (N^2)]

삽입 정렬 [기기 : O (N), 최악 : O (N^2)]

퀵 [기기 : O (N LG N) 부근 : O (Ng N), 최악 : O (N^2)]

힙 정렬 (Heapsort) [최고/평균/최악 : O (N의 LG N)]

정렬 계산 [베스트/평균/최악 : O (N)]

기수 정렬 [베스트/평균/최악 : O (N)]

소스 위키 Sorting

우리가 동일한 데이터 세트에 대한 고전 거품 정렬 알고리즘하여 상기 알고리즘을 비교할 수 있습니다. 이 테스트 코드입니다 :

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

static int count = 0; 

int main(void) { 

    char name[10][8], tname[10][8], temp[8]; 
    int i, j, n; 

    printf("Enter the number of names\n"); 
    scanf("%d", &n); 
    printf("Enter %d names\n", n); 

    // reading names 
    for (i = 0; i < n; i++) 
    { 
     scanf("%s", name[i]); 
     strcpy(tname[i], name[i]); 
    } 

    // standard bubble sort 
    for (i = 0; i < n - 1 ; i++) 
    { 
     for (j = i + 1; j < n; j++) 
     { 
      if (strcmp(name[i], name[j]) > 0) 
      { 
       strcpy(temp, name[i]); 
       strcpy(name[i], name[j]); 
       strcpy(name[j], temp); 

       count = count + 1; 
       printf("swap %d ", count); 
      } 
     } 
    } 

    // Print results: 
    printf("\n----------------------------------------\n"); 
    printf("Input Names \tSorted names\n"); 
    printf("------------------------------------------\n"); 
    for (i = 0; i < n; i++) 
    { 
     printf("%s\t\t\t%s\n", tname[i], name[i]); 
    } 
    printf("------------------------------------------\n"); 
    return 0; 
} 

입력 :

7 dHea bbcx abcd cbcd cbad bbcd cbaa 

그 결과, 우리가 필요로 동일한 데이터 세트에 대한 그래서

Enter the number of names 
Enter 7 names 
swap 1 swap 2 swap 3 swap 4 swap 5 swap 6 swap 7 swap 8 swap 9 swap 10 swap 11 swap 12 swap 13 
---------------------------------------- 
Input Names  Sorted names 
------------------------------------------ 
dHea   abcd 
bbcx   bbcd 
abcd   bbcx 
cbcd   cbaa 
cbad   cbad 
bbcd   cbcd 
cbaa   dHea 

---

reference

13 sw aps는 버블 정렬 알고리즘에서 알파 알고리즘처럼 8 대신에 사용됩니다.

(이 특정 버블 정렬은 strcpy 함수 대 스와핑 포인터를 사용합니다.)

나의 결론은 "알파 정렬"알고리즘이 일 때 항상이 고전적인 버블 정렬보다 더 효율적이라는 것입니다. 이는 정렬 된 목록에 요소를 순차적으로 정렬하기 시작하기 때문입니다. 기본적으로이 알고리즘을 개선 된 버블 정렬로 처리 할 수 ​​있습니다.

증가하는 목록은 항상 정렬되므로 일부 유형의 응용 프로그램에 매우 유용 할 수 있습니다.