473,902 Members | 4,620 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

Best regards,
Kent
Nov 13 '05
10 15147

"pete" <pf*****@mindsp ring.com> wrote in message
news:3F******** **@mindspring.c om...
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
2177
by: dam_fool_2003 | last post by:
friends, I wanted to learn the various ways of inserting a single list. so: Method 1: #include<stdlib.h> #include<stdio.h> struct node { unsigned int data; struct node *next;
57
4328
by: Xarky | last post by:
Hi, I am writing a linked list in the following way. struct list { struct list *next; char *mybuff; };
4
2080
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
8165
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 maximum value N 2. loop through 1...N 3. count # times each occurred
6
16138
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: struct node { int x; struct node *next; };
17
3056
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 else? The reason for this question is that I had an assignment in which I was
22
8057
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 solution. Being that recursion is frowned upon in embedded software, the answer was not what the interviewer expected, but alas it was correct. I asked some friends how they would have answered and another answer is to reverse the list and then...
1
4410
by: hanna88 | last post by:
what's the best way to convert a list of string to a vector<int>? what i have now is for loop and iterate each char in the string string base=""; //i have vector<int>row,vector < vector<int>row > mat; //what i want to do with the string is that everytime char != ";" row.pushback(str that convert to int)
1
6744
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 case:2 -to count the no. of collisions in the hash table, case:3 -to show the values of hash table, case:4 -to search a value using the hash table. use roll no of the student to be stored in hash table using double linked list. #include...
0
9997
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
1
10981
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9675
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
8047
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7205
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5893
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6085
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
4307
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3323
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.