Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Best method to sort a linked list (in my case)?

Reply
Thread Tools

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

 
 
Kent
Guest
Posts: n/a
 
      10-21-2003
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


 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      10-21-2003
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 about this. Please excouse my poor english, it is not my native
> 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.

--
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
 
 
 
Kent
Guest
Posts: n/a
 
      10-21-2003
> 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.


 
Reply With Quote
 
Christian Bau
Guest
Posts: n/a
 
      10-21-2003
In article <(E-Mail Removed)>,
Eric Sosman <(E-Mail Removed)> 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
> > programmers about this. Please excouse my poor english, it is not my native
> > 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.
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      10-22-2003
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
> some opinions from more experienced programmers about this.
> 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:

<http://cbfalconer.home.att.net/download/>

--
Chuck F ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!


 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      10-23-2003
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 */
 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      10-23-2003
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[2];

if (count > 1) {
pointer[0] = base;
half = source = count / 2;
while (--half != 0) {
base = base -> NEXT;
}
pointer[1] = base -> NEXT;
pointer[1] -> PREV = base -> NEXT = 0;
half = source;
pointer[0] = l_sort(pointer[0], half);
pointer[1] = l_sort(pointer[1], count - half);
source = GTE(pointer[1], pointer[0]) ? 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
 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      10-23-2003
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[2];

if (count > 1) {
pointer[0] = base;
source = half = count / 2;
while (--source != 0) {
base = base -> NEXT;
}
pointer[1] = base -> NEXT;
pointer[1] -> PREV = base -> NEXT = 0;
pointer[0] = l_sort(pointer[0], half);
pointer[1] = l_sort(pointer[1], count - half);
source = GTE(pointer[1], pointer[0]) ? 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
 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      10-23-2003
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[2];

if (count > 1) {
pointer[0] = base;
source = half = count / 2;
while (--source != 0) {
base = base -> NEXT;
}
pointer[1] = base -> NEXT;
pointer[1] -> PREV = base -> NEXT = 0;
pointer[0] = l_sort(pointer[0], half);
pointer[1] = l_sort(pointer[1], count - half);
source = GTE(pointer[1], pointer[0]) ? 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
 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      10-24-2003
/*
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
about this.
*/

/*
** 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[2];

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

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

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

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

--
pete
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments