Kent wrote:
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;
// 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.
Check out the funky goto, in l_sort().
/* BEGIN node.c */
#include <stdio.h>
#include <stdlib.h>
#define NODES 20
#define GTE(A, B) ((A) -> y >= (B) -> y)
#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) = (S) * 69069 + 362437 & 0xffffffff)
struct node {
double x, y;
struct enemy *enemydata;
struct node *prev;
struct node *next;
};
void l_free(struct node *);
struct node *l_make(size_t);
long unsigned l_init(struct node *, long unsigned);
void l_print(struct node *);
struct node *l_sort(struct node *, const size_t);
int main(void)
{
struct node *head;
head = l_make(NODES);
if (head) {
l_init(head, LU_RAND_SEED);
l_print(head);
head = l_sort(head, NODES);
l_print(head);
l_free(head);
} else {
puts("The list was not allocated.");
}
return 0;
}
void l_free(struct node *pointer)
{
while (pointer) {
struct node *next = pointer -> next;
free(pointer);
pointer = next;
}
}
struct node *l_make(size_t nodes)
{
struct node *pointer, *head;
head = nodes ? malloc(sizeof *pointer) : NULL;
if (head) {
pointer = head;
pointer -> prev = NULL;
while (--nodes != 0) {
pointer -> next = malloc(sizeof *pointer -> next);
if (!pointer -> next) {
l_free(head);
return NULL;
}
pointer -> next -> prev = pointer;
pointer = pointer -> next;
}
pointer -> next = NULL;
}
return head;
}
long unsigned l_init(struct node *pointer, long unsigned seed)
{
while (pointer) {
pointer -> y = 3.14159265 * LU_RAND(seed);
pointer = pointer -> next;
}
return seed;
}
void l_print(struct node *pointer)
{
while (pointer) {
printf("pointer -> y is %f\n", pointer -> y);
pointer = pointer -> next;
}
putchar('\n');
}
struct node *l_sort(struct node *base, const size_t count)
{
size_t half, source;
struct {
struct node *head;
struct node *pointer;
} list[2];
if (2 > count) {
return base;
}
list[0].pointer = list[0].head = base;
half = count / 2;
while (--half != 0) {
list[0].pointer = list[0].pointer -> next;
}
list[1].head = list[0].pointer -> next;
list[1].head -> prev = list[0].pointer -> next = NULL;
half = count / 2;
list[0].head = l_sort(list[0].head, half);
list[1].head = l_sort(list[1].head, count - half);
list[0].pointer = list[0].head;
list[1].pointer = list[1].head;
source = GTE(list[1].head, list[0].head) ? 0 : 1;
base = list[source].head;
outer_loop_top:
while (list[source].pointer -> next) {
list[source].pointer = list[source].pointer -> next;
while(GTE(list[source ^ 1].pointer, list[source].pointer)){
goto outer_loop_top;
}
list[source].pointer->prev->next = list[source ^ 1].pointer;
list[source ^ 1].pointer->prev = list[source].pointer->prev;
source ^= 1;
}
list[source].pointer -> next = list[source ^ 1].pointer;
list[source ^ 1].pointer -> prev = list[source].pointer;
return base;
}
/* END node.c */
