472,805 Members | 1,183 Online

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

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
language.

Best regards,
Kent
Nov 13 '05 #1
10 15007 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; // 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
language.

This does not seem to be a question about C, but about
choosing an algorithm. comp.graphics.algorithms would be a
better forum for your question. You will probably want to
use an algorithm that takes advantage of the fact that your
list is "almost sorted" to begin with, even if that method
is not especially good for "random" lists.

--
Er*********@sun.com
Nov 13 '05 #2
> This does not seem to be a question about C, but about
choosing an algorithm. comp.graphics.algorithms would be a
better forum for your question. You will probably want to
use an algorithm that takes advantage of the fact that your
list is "almost sorted" to begin with, even if that method
is 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
In article <3F***************@sun.com>,
Eric Sosman <Er*********@sun.com> wrote:
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; // 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
language.

This does not seem to be a question about C, but about
choosing an algorithm. comp.graphics.algorithms would be a
better forum for your question. You will probably want to
use an algorithm that takes advantage of the fact that your
list is "almost sorted" to begin with, even if that method
is not especially good for "random" lists.

shakersort (bubblesort in alternating directions) is quite good for this
situation, and works quite well with a doubly linked list.
Nov 13 '05 #4
Kent wrote:

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
// 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
Please excouse my poor english, it is not my native language.

Definitely mergesort, because it will work on the lists directly.
It is also O(NlogN) at all times. You can find an example in
wdfreq.c demo in hashlib.zip, at:

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
Nov 13 '05 #5
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
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)
{

} 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)
{

head = nodes ? malloc(sizeof *pointer) : NULL;
pointer -> prev = NULL;
while (--nodes != 0) {
pointer -> next = malloc(sizeof *pointer -> next);
if (!pointer -> next) {
return NULL;
}
pointer -> next -> prev = pointer;
pointer = pointer -> next;
}
pointer -> next = NULL;
}
}

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 *pointer;
} list;

if (2 > count) {
return base;
}
half = count / 2;
while (--half != 0) {
list.pointer = list.pointer -> next;
}
list.head -> prev = list.pointer -> next = NULL;
half = count / 2;
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 */
Nov 13 '05 #6
pete wrote:
struct node *l_sort(struct node *base, const size_t count)

/* BEGIN l_sort.c */

#include <stddef.h>

#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
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
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
/*
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;
// 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
*/

/*
** Mergesort is extremely well suited to sorting linked lists.
*/

/* BEGIN listsort.c */
/*
** l_sort() is a nonstable sorting function for doubley linked lists.
** ls_sort() is a nonstable sorting function for singley linked lists.
** sl_sort() is a stable sorting function for doubley linked lists.
** sls_sort() is a stable sorting function for singley linked lists.
** If the parameters "list" and "count" don't correspond to
** the head of the list, and the tail of the list,
** then the sorting functions won't work right.
*/
#include <stdio.h>
#include <stdlib.h>

#define NODES 16
/*
** These next 4 macros, are the ones that you would change,
** to use l_sort() on a double linked list of any other type node.
** l_init() and l_print(), as written, will only work with a
** node which has a member named y, of type double.
*/
#define N_TYPE \
struct node {double x, y; struct node *prev; struct node *next;}
#define GT(A, B) ((A) -> y > (B) -> y)
#define PREV prev
#define NEXT next

typedef N_TYPE n_type;

#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) = (S) * 69069 + 362437 & 0xffffffff)

void l_free (n_type *);
n_type *l_make (size_t);
long unsigned l_init (n_type *, long unsigned);
void l_print(n_type *);
n_type *l_sort (n_type *, size_t);
n_type *sl_sort (n_type *, size_t);
n_type *ls_sort (n_type *, size_t);
n_type *sls_sort (n_type *, size_t);

int main(void)
{
n_type *list;

list = l_make(NODES);
if (list) {
l_init(list, LU_RAND_SEED);
puts("Random order");
l_print(list);
list = l_sort(list, NODES);
puts("Sorted order");
l_print(list);
l_free(list);
} else {
puts("The list was not allocated.");
}
return 0;
}

void l_free(n_type *pointer)
{
while (pointer) {
n_type *NEXT = pointer -> NEXT;

free(pointer);
pointer = NEXT;
}
}

n_type *l_make(size_t nodes)
{
n_type *pointer, *list;

list = nodes ? malloc(sizeof *list) : NULL;
if (list) {
pointer = list;
pointer -> PREV = NULL;
while (--nodes != 0) {
pointer -> NEXT = malloc(sizeof *pointer -> NEXT);
if (!pointer -> NEXT) {
l_free(list);
return NULL;
}
pointer -> NEXT -> PREV = pointer;
pointer = pointer -> NEXT;
}
pointer -> NEXT = NULL;
}
return list;
}

long unsigned l_init(n_type *pointer, long unsigned seed)
{
while (pointer) {
pointer -> y = 3.14159265 * LU_RAND(seed);
pointer = pointer -> NEXT;
}
return seed;
}

void l_print(n_type *pointer)
{
while (pointer) {
printf("pointer -> y is %f\n", pointer -> y);
pointer = pointer -> NEXT;
}
putchar('\n');
}

n_type *l_sort(n_type *list, size_t count)
{
size_t half, source;
n_type *pointer;

if (count > 1) {
source = half = count / 2;
pointer = list;
do {
pointer = pointer -> NEXT;
} while (--source != 0);
pointer -> PREV -> NEXT = 0;
pointer -> PREV = 0;
pointer = l_sort(pointer, count - half);
pointer = l_sort(list, half);
if (GT(pointer, pointer)) {
source = 1;
}
list = 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 list;
}

n_type *sl_sort(n_type *list, size_t count)
{
size_t half, source;
n_type *pointer;

if (count > 1) {
source = half = count / 2;
pointer = list;
do {
pointer = pointer -> NEXT;
} while (--source != 0);
pointer -> PREV -> NEXT = 0;
pointer -> PREV = 0;
pointer = l_sort(pointer, count - half);
pointer = l_sort(list, half);
if (GT(pointer, pointer)) {
source = 1;
}
list = pointer[source];
while (pointer[source] -> NEXT) {
pointer[source] = pointer[source] -> NEXT;
if (!source) {
if (GT(pointer, pointer)) {
pointer -> PREV -> NEXT = pointer;
pointer -> PREV = pointer -> PREV;
source ^= 1;
}
} else {
if (!GT(pointer, pointer)) {
pointer -> PREV -> NEXT = pointer;
pointer -> PREV = pointer -> PREV;
source ^= 1;
}
}
}
pointer[source ] -> NEXT = pointer[source ^ 1];
pointer[source ^ 1] -> PREV = pointer[source ];
}
return list;
}

n_type *ls_sort(n_type *list, size_t count)
{
size_t half, source;
n_type *pointer, *prev_pointer;

if (count > 1) {
source = half = count / 2;
prev_pointer = list;
while (--source != 0) {
prev_pointer = prev_pointer -> NEXT;
}
pointer = prev_pointer -> NEXT;
prev_pointer -> NEXT = 0;
pointer = l_sort(pointer, count - half);
pointer = l_sort(list, half);
if (GT(pointer, pointer)) {
source = 1;
}
list = pointer[source];
while (pointer[source] -> NEXT) {
prev_pointer = pointer[source];
pointer[source] = pointer[source] -> NEXT;
if (GT(pointer[source], pointer[source ^ 1])) {
prev_pointer -> NEXT = pointer[source ^ 1];
source ^= 1;
}
}
pointer[source] -> NEXT = pointer[source ^ 1];
}
return list;
}

n_type *sls_sort(n_type *list, size_t count)
{
size_t half, source;
n_type *pointer, *prev_pointer;

if (count > 1) {
source = half = count / 2;
prev_pointer = list;
while (--source != 0) {
prev_pointer = prev_pointer -> NEXT;
}
pointer = prev_pointer -> NEXT;
prev_pointer -> NEXT = 0;
pointer = l_sort(pointer, count - half);
pointer = l_sort(list, half);
if (GT(pointer, pointer)) {
source = 1;
}
list = pointer[source];
while (pointer[source] -> NEXT) {
prev_pointer = pointer[source];
pointer[source] = pointer[source] -> NEXT;
if (!source) {
if (GT(pointer, pointer)) {
prev_pointer -> NEXT = pointer;
source ^= 1;
}
} else {
if (!GT(pointer, pointer)) {
prev_pointer -> NEXT = pointer;
source ^= 1;
}
}
}
pointer[source] -> NEXT = pointer[source ^ 1];
}
return list;
}
/* END listsort.c */

--
pete
Nov 13 '05 #10

"pete" <pf*****@mindspring.com> wrote in message
news:3F**********@mindspring.com...
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).

Well there are several solutions. You could just make an array of lists for
each possible y. If there are too many you could try a heap instead which
has the benefit of using fixed storage [cuz generally for games you want to
use a fixed amount of heap lest you run into a "out of memory" message half
way through a hard level... stupid jedi knights].

If you really want to use a linked list you could indecies into the list for
the start of each y. That way you can insert in O(1) time [best case] and
near O(n) worst case [which won't happen often]. So say you want to insert
you look into the index for the given y. If it's found you insert and
adjust the neighbours next/prev pointers. If it isn't found you move up the
index table until you find a non NULL and then step through the list until
you find the last value.

e.g. say you want y=6 but there are no index markings for y=6. You then
look at y=5. Say there is a y=5. You step through the list until you find
an entry with y != 5 and you wedge your item between.

Eventually all of the indecies likely to be used will have hits and inserts
will take O(1) time.

So along as you have a feasible number of y values [say 768 or whatever] the
index will be small [e.g. <4KB]

Tom
Nov 13 '05 #11

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 7 by: dam_fool_2003 | last post by: friends, I wanted to learn the various ways of inserting a single list. so: Method 1: #include #include struct node { unsigned int data; struct node *next; 57 by: Xarky | last post by: Hi, I am writing a linked list in the following way. struct list { struct list *next; char *mybuff; }; 4 by: Peter Schmitz | last post by: Hi, in my application, I defined a linked list just as follows: typedef struct _MYLIST{ int myval; void *next; }MYLIST; MYLIST head; 21 by: Imran | last post by: I have a vector of integers, such as and I want to find out the number which occurs most frequently.what is the quick method. My array size is huge. what I am doing is 1. find out the... 6 by: Julia | last post by: I am trying to sort a linked list using insertion sort. I have seen a lot of ways to get around this problem but no time-efficient and space-efficient solution. This is what I have so far: ... 17 by: 2005 | last post by: Hi In C++, are the following considered best practices or not? - passing aguments to functions (ie functions do not take any arguments ) - returning values using return statement Anything... 22 by: joshc | last post by: In an interview for an embedded software position recently I was asked to write code, in C, for printing the contents of a linked list backwards. After a few minutes I came up with the recursive... 1 by: hanna88 | last post by: what's the best way to convert a list of string to a vector? what i have now is for loop and iterate each char in the string string base=""; //i have vectorrow,vector <... 1 by: monalisa mohanty | last post by: please help me to complete the below written c++ program code. i have witten the code to insert student's information(case:1) and display it using linked list(case:5). Help me to write the code for... 2 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 2 August 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central... 0 by: linyimin | last post by: Spring Startup Analyzer generates an interactive Spring application startup report that lets you understand what contributes to the application startup time and helps to optimize it. Support for... 0 by: kcodez | last post by: As a H5 game development enthusiast, I recently wrote a very interesting little game - Toy Claw ((http://claw.kjeek.com/))。Here I will summarize and share the development experience here, and hope it... 2 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 6 Sept 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central... 14 by: DJRhino1175 | last post by: When I run this code I get an error, its Run-time error# 424 Object required...This is my first attempt at doing something like this. I test the entire code and it worked until I added this - If... 0 by: Rina0 | last post by: I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in... 5 by: DJRhino | last post by: Private Sub CboDrawingID_BeforeUpdate(Cancel As Integer) If = 310029923 Or 310030138 Or 310030152 Or 310030346 Or 310030348 Or _ 310030356 Or 310030359 Or 310030362 Or... 0 by: lllomh | last post by: Define the method first this.state = { buttonBackgroundColor: 'green', isBlinking: false, // A new status is added to identify whether the button is blinking or not } autoStart=()=>{ 0 by: lllomh | last post by: How does React native implement an English player?