425,967 Members | 843 Online Need help? Post your question and get tips & solutions from a community of 425,967 IT Pros & Developers. It's quick & easy.

# Best method to sort a linked list (in my case)?

 P: n/a Hi! I want to store data (of enemys in a game) as a linked list, each node will look something like the following: struct node { double x,y; // x and y position coordinates struct enemy *enemydata; // Holds information about an enemy (in a game) // Its a double linked list node struct node *prev; struct node *next; }; Each node´s x and y coordinates in the linked list changes for every frame. Before drawing the enemys to the game screen (graphic memory) i would like to sort the entire list based on the y coordinate (lowest first). My question is, wich sort algorithm do you recommend? As it is a linked list, i thought that insertion sort would work as a linked list is insertion sort´s "best case". But i would like some opinions from more experienced programmers about this. Please excouse my poor english, it is not my native language. Best regards, Kent Nov 13 '05 #1
10 Replies

 P: n/a > This does not seem to be a question about C, but aboutchoosing an algorithm. comp.graphics.algorithms would be abetter forum for your question. You will probably want touse an algorithm that takes advantage of the fact that yourlist is "almost sorted" to begin with, even if that methodis not especially good for "random" lists. It isn´t about a graphical algorithm either. If someone else has an actual answer i would appreciate it much. Nov 13 '05 #3

 P: n/a pete wrote: struct node *l_sort(struct node *base, const size_t count) /* BEGIN l_sort.c */ #include #define GTE(A, B) ((A) -> y >= (B) -> y) #define PREV prev #define NEXT next #define N_TYPE struct node typedef N_TYPE n_type; struct node { double x, y; struct enemy *enemydata; struct node *prev; struct node *next; }; n_type *l_sort(n_type *, const size_t); n_type *l_sort(n_type *base, const size_t count) { size_t half, source; n_type *pointer; if (count > 1) { pointer = base; half = source = count / 2; while (--half != 0) { base = base -> NEXT; } pointer = base -> NEXT; pointer -> PREV = base -> NEXT = 0; half = source; pointer = l_sort(pointer, half); pointer = l_sort(pointer, count - half); source = GTE(pointer, pointer) ? 0 : 1; base = pointer[source]; loop_top: while (pointer[source] -> NEXT) { pointer[source] = pointer[source] -> NEXT; if (GTE(pointer[source ^ 1], pointer[source])) { goto loop_top; } pointer[source] -> PREV -> NEXT = pointer[source ^ 1]; pointer[source ^ 1] -> PREV = pointer[source] -> PREV; source ^= 1; } pointer[source] -> NEXT = pointer[source ^ 1]; pointer[source ^ 1] -> PREV = pointer[source]; } return base; } /* END l_sort.c */ -- pete Nov 13 '05 #7

 P: n/a pete wrote: base = pointer[source]; loop_top: while (pointer[source] -> NEXT) { pointer[source] = pointer[source] -> NEXT; if (GTE(pointer[source ^ 1], pointer[source])) { goto loop_top; } "continue" is the word I was looking for. n_type *l_sort(n_type *base, const size_t count) { size_t half, source; n_type *pointer; if (count > 1) { pointer = base; source = half = count / 2; while (--source != 0) { base = base -> NEXT; } pointer = base -> NEXT; pointer -> PREV = base -> NEXT = 0; pointer = l_sort(pointer, half); pointer = l_sort(pointer, count - half); source = GTE(pointer, pointer) ? 0 : 1; base = pointer[source]; while (pointer[source] -> NEXT) { pointer[source] = pointer[source] -> NEXT; if (GTE(pointer[source ^ 1], pointer[source])) { continue; } pointer[source] -> PREV -> NEXT = pointer[source ^ 1]; pointer[source ^ 1] -> PREV = pointer[source] -> PREV; source ^= 1; } pointer[source] -> NEXT = pointer[source ^ 1]; pointer[source ^ 1] -> PREV = pointer[source]; } return base; } -- pete Nov 13 '05 #8

 P: n/a pete wrote: pete wrote: base = pointer[source]; loop_top: while (pointer[source] -> NEXT) { pointer[source] = pointer[source] -> NEXT; if (GTE(pointer[source ^ 1], pointer[source])) { goto loop_top; } "continue" is the word I was looking for. No, it wasn't. n_type *l_sort(n_type *base, const size_t count) { size_t half, source; n_type *pointer; if (count > 1) { pointer = base; source = half = count / 2; while (--source != 0) { base = base -> NEXT; } pointer = base -> NEXT; pointer -> PREV = base -> NEXT = 0; pointer = l_sort(pointer, half); pointer = l_sort(pointer, count - half); source = GTE(pointer, pointer) ? 0 : 1; base = pointer[source]; while (pointer[source] -> NEXT) { pointer[source] = pointer[source] -> NEXT; if (GT(pointer[source], pointer[source ^ 1])) { pointer[source] -> PREV -> NEXT = pointer[source ^ 1]; pointer[source ^ 1] -> PREV = pointer[source] -> PREV; source ^= 1; } } pointer[source] -> NEXT = pointer[source ^ 1]; pointer[source ^ 1] -> PREV = pointer[source]; } return base; } -- pete Nov 13 '05 #9 