sorting - How do I sort a linked list in a alphabetical order in c -
i'm trying sort linked list in alphabetical order, looks sorting algorithm doesn't. how can sort list?
typedef struct s_file { char *file_name; struct s_file *next; } t_file; void sort_alpha(t_file **begin_list) { t_file *list; char *tmp; list = *begin_list; if (list) { while (list) { 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; } list = list->next; } } }
after looking @ code once more have optimized match original intention of @tenten peter. outer loop not needed. sorting done correctly:
#include <stdlib.h> #include <stdio.h> #include <dirent.h> #include <string.h> // definition of 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; // point each node traverses 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 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 list , sorting @ 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); // done by: // read_dir(av[1], &s); // untested // print 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; } output:
*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 here: code
edit: since 1 may have concerns regarding efficiency of above algorithm have added swap counter. counts how many times need swap pointers had occurred. (please note no copying of involved). above data algorithm seems efficient. 8 swaps our list of 7 elements!
to compare these sorting times various sorting algorithms:
bubble sort [best: o(n), worst:o(n^2)]
selection sort [best/worst: o(n^2)]
insertion sort [best: o(n), worst:o(n^2)]
quicksort [best: o(n lg n), avg: o(n lg n), worst:o(n^2)]
heapsort [best/avg/worst: o(n lg n)]
counting sort [best/avg/worst: o(n)]
radix sort [best/avg/worst: o(n)]
source wiki sorting
lets compare above algorithm classical bubble sort algorithm same set of data. testing code:
#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 number of names\n"); scanf("%d", &n); printf("enter %d names\n", n); // reading names (i = 0; < n; i++) { scanf("%s", name[i]); strcpy(tname[i], name[i]); } // standard bubble sort (i = 0; < n - 1 ; i++) { (j = + 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"); (i = 0; < n; i++) { printf("%s\t\t\t%s\n", tname[i], name[i]); } printf("------------------------------------------\n"); return 0; } input:
7 dhea bbcx abcd cbcd cbad bbcd cbaa the result:
enter 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 so same set of data needed 13 swaps in bubble sort algorithm instead of 8 in alpha algorithm.
(this particular bubble sort uses strcpy function versus swapping pointers.)
my conclusion presented "alpha sort" algorithm always more efficient classical bubble sort. due fact start sorting right away successively adding elements sorted list. can treat algorithm improved bubble sort.
it worth note growing list sorted can useful types of applications.
Comments
Post a Comment