[RESOLVED] Sorting small arrays. Witch algo is fastest.

I need someone to fresh up my memory here since I don't have any of my algorithm books around.

I have a small array, about 144 pointer (32bits each). So this is NOT much data. And an other importent thing is that the data in the array will always NEARLY be sorted before you start. I guess that is importent info since sorting algorithms as Quicksort has it's worst case when the array is nearl sorted.


So can anyone enlighten me a bit on what algo would be the fastest on this tiny array that is all ready nearly sorted?

Thanks
- ØØ

Bubble sort.... :D j/k

Sorting algorithms

It didn't give much info on small arrays. It is impossible to see witch one is fastest when you talk about less then 1000 objects. And the page only talks about the average. Doesn't care about worst case and so on. And this is a worst case small array question.

And it adds comments like this:

Quote:

---

Ironically, the quick sort has horrible efficiency when operating on lists that are mostly sorted in either forward or reverse order - avoid it in those situations.

---

Without saying what you should choose in stead....witch brings me back to where I started...:(


- ØØ -

I see the problem.

Here's more...

Quote:

---

Originally Posted by Wiki

Shell sort ... is one of the fastest algorithms for sorting small numbers of elements (sets with less than 1000 or so elements).

---

Hope that helps a bit more :)

Now we are starting to get somewhere here..:). It still doesn't say anyithing as far as I can see about all ready nearly sorted lists though. But it is a LOT to read here. So it is going to take a few years before I find out I guess..:D



[Edit] Looks like I have rated you not too long ago, so I can't do it again..:( Post is bookmarked though.



Thanks
- ØØ -

No worries :)

I have read something about how quicksort is very inefficient with nearly sorted arrays (as you said), and there are others that are unaffected. But, rather like you, I can't remember which... :D

If its nearly sorted from the start then I reckon insertion sort will beat all others, even if there are 144 elements. Alternatively shell sort if its not so sorted from the start.

Hehe..if this thread keeps going in this direction I guess we have to make one function for each sorting and test witch one is the fastest. I think Merge sort can be pretty fast on this too, don't you think so? Uses a bit more memory then most of the others, but that doesn't do to much since it is only 144 indexes to sort....

- ØØ -

Quote:

---

Originally Posted by NoteMe

Hehe..if this thread keeps going in this direction I guess we have to make one function for each sorting and test witch one is the fastest.

---

I see you are still typing witch instead of which, but if you think its faster to type then you are wrong ;)

Quote:

---

I think Merge sort can be pretty fast on this too, don't you think so? Uses a bit more memory then most of the others, but that doesn't do to much since it is only 144 indexes to sort....

- ØØ -

---

Its possible to use merge sort but it wont have the speed benefits, you'll just be throwing around the indexes. Anyway, are the indexes relatively close to each other? You might get away with something like radix or bucket sort.

Quote:

---

Originally Posted by kedaman

I see you are still typing witch instead of which, but if you think its faster to type then you are wrong ;)

---

Grrr...give me a break here..:D

I'll try to remember it this time..:)..it is a linux command too, and I always have to try 3-4 times before I manage to write it right...:D

Quote:

---

Originally Posted by kedaman

Its possible to use merge sort but it wont have the speed benefits, you'll just be throwing around the indexes. Anyway, are the indexes relatively close to each other? You might get away with something like radix or bucket sort.

---

What do you mean by indexes relatively close? I have never read up on Radix or bucket sort. Just heard about them. So no idea how they will affect this.

Ok, just to get you more up to date on what is goin on here. This is for D# right. And what I am sorting is the polygons that we will draw. We sort them from the back to the front. It is maximum about 144 polygons to draw at any time on our maps. So I don't think it will be nessesary to use a BSP with painters algorithm and all that fancy stuff. The thing is that since you don't turn around so fast most often in the game, you are most likely sorting more or less the same polygons each time. Hence the array you are sorting will nearly be sorted every time.

I just tested with shell sort. And it tool less then 0.2FPS to sort about 144polygons. So I don't think it will be that big a difference no matter what sorting algo we use.

BTW there where some artifacts on the picture. I have too look into what went wrong.

- ØØ -

Quote:

---

Originally Posted by NoteMe

Grrr...give me a break here..:D

I'll try to remember it this time..:)..it is a linux command too, and I always have to try 3-4 times before I manage to write it right...:D

---

Unless you have me reminding you about all the time, nobody knows what sort of schwahili your english is transmutating into ;)

Quote:

---

What do you mean by indexes relatively close? I have never read up on Radix or bucket sort. Just heard about them. So no idea how they will affect this.

---

That they are about a certain distance from each other. Radix sort and bucket sort only works if you sort things within certain limits. Anyway I guess it might be best to either run shellsort or just raw insertion sort, which I think after hearing what you use it for might be best.

Quote:

---

BTW there where some artifacts on the picture. I have too look into what went wrong.

- ØØ -

---

can you post a screenshot?

Here you go....I still havn't tested if the sorting algo is working though..:)..and I have one other idea too. But at least here is the result. The one to the left is without sorting, and the one to the right is with sorting.

The list is definitly sorted. but I find it weird that so many wallparts have the same distance. I think the problem is the calculation of the distance then..:)


Distance:

Quote:

---

20.45593
20.45593
20.45593
20.45593
20.45593
20.45593
20.45593
20.45593
20.45593
20.45593
19.55126
19.55126
19.55126
19.55126
19.55126
19.55126
19.55126
19.55126
19.55126
19.55126
19.45887
19.45887
19.4176
19.4176
19.4176
19.4176
19.4176
19.4176
19.4176
19.4176
19.4176
19.4176
18.46212
18.46212
18.46212
17.56863
17.56863
17.56863
17.56863
17.56863
17.56863
17.56863
17.56863
17.56863
17.46575
17.46575
17.46575
17.46575
17.46575
17.46575
17.46575
17.46575
17.41976
17.41976
17.41976
17.41976
17.41976
17.41976
17.41976
17.41976
17.41976
16.46982
16.46982
16.46982
16.46982
16.46982
15.59043
15.59043
15.59043
15.59043
15.59043
15.59043
15.59043
15.59043
15.59043
15.59043
15.4744
15.4744
15.4744
15.4744
15.4744
15.4744
15.4744
15.4744
15.4744
15.4744
15.42248
15.42248
15.42248
15.42248
15.42248
15.42248
15.42248
15.42248
15.42248
15.42248
14.47963
14.47963
14.47963
14.47963
14.47963
13.6186
13.6186
13.6186
13.6186
13.6186
13.6186
13.6186
13.6186
13.6186
13.48562
13.48562
13.48562
13.48562
13.48562
13.48562
13.48562
13.48562
13.48562
13.48562
13.42601
13.42601
13.42601
13.42601
13.42601
13.42601
13.42601
13.42601
13.42601
12.49257
12.49257
12.49257
12.49257
12.49257
12.49257
11.65637
11.65637
11.65637
11.65637
11.65637
11.65637
11.65637
11.65637
11.65637
11.50073
11.50073
11.50073
11.50073
11.50073
11.50073
11.50073
11.50073
11.43077
11.43077
11.43077
11.43077
11.43077
11.43077
11.43077
11.43077
11.43077
10.51043
9.709574
9.709574
9.709574
9.709574
9.709574
9.709574
9.709574
9.709574
9.709574
9.709574
9.522162
9.522162
9.522162
9.522162
9.522162
9.522162
9.522162
9.522162
9.43755
9.43755
9.43755
9.43755
9.43755
9.43755
9.43755
9.43755
9.43755
9.43755
8.536626
8.536626
8.536626
8.536626
7.789777
7.789777
7.789777
7.789777
7.789777
7.789777
7.789777
7.789777
7.789777
7.789777
7.554892
7.554892
7.554892
7.554892
7.554892
7.554892
7.554892
7.554892
7.554892
7.554892
7.554892
7.554892
7.447962
7.447962
7.447962
7.447962
7.447962
7.447962
7.447962
7.447962
7.447962
7.447962
6.578661
6.578661
5.923295
5.923295
5.923295
5.923295
5.923295
5.923295
5.923295
5.923295
5.610809
5.610809
5.610809
5.610809
5.610809
5.610809
5.610809
5.610809
5.610809
5.610809
5.610809
5.610809
5.46598
5.46598
5.46598
5.46598
5.46598
5.46598
5.46598
5.46598
4.656563
4.656563
4.656563
4.656563
4.656563
4.656563
4.656563
4.182131
4.182131
4.182131
4.182131
4.182131
4.182131
4.182131
4.182131
4.182131
3.726389
3.726389
3.50453
3.50453
3.50453
3.50453
3.50453
3.50453
3.50453
3.50453
3.50453
2.844006
2.844006
2.844006
2.844006
2.844006
2.809807
2.809807
2.809807
2.809807
2.071417
2.071417
1.639062
1.639062
1.639062
1.639062
1.578976
1.578976
1.578976
1.578976

---

It looks like some front facing walls are getting overdrawn by tiles behind them, are you sure that you're sorting the right values?

definitively the distance calcuation then ;)

hehe..yeah it was...I am not sure if it is the right way to do it. You might want to comment on it but, I am taking the four X coordinates of a quad, sum the X coord up and then devide on 4. Then do the same on the Y value, and stores the "midle" position of the quad. That will will be right, right?

Here is the code for it (the error was that I used X and Y instead of X and Z...:rolleyes:

Code:

---

float distX = (wPoints[0].X + wPoints[1].X + wPoints[2].X + wPoints[3].X) / 4;
            float distZ = (wPoints[0].Z + wPoints[1].Z + wPoints[2].Z + wPoints[3].Z) / 4;
            Position = new Vector(distX, distZ, 1.5f);

---

- ØØ -

I can't comment on the syntax, but the idea of summing co-ordinates and dividing by the count is correct for a regular polygon (quad, triangle, etc).

Nah, just pick the one vector which is closest Z wise, and sort by those z values.

Quote:

---

Originally Posted by si_the_geek

I can't comment on the syntax, but the idea of summing co-ordinates and dividing by the count is correct for a regular polygon (quad, triangle, etc).

---

The syntax is always right...it is me we are talking about here...:) Thanks Si.


DoomSharp(); - Will make you smile.


- ØØ -

Quote:

---

Originally Posted by kedaman

Nah, just pick the one vector which is closest Z wise, and sort by those z values.

---

But that is going to change the whole time...the position in world coordinates will not change at all during run time...


- ØØ -

I disagree, the issues in the picture above can be caused by that for two "walls" that meet at the corners, as the closest points are the same for both of them.

You should stick to the centre points :)

Quote:

---

Originally Posted by NoteMe

But that is going to change the whole time...the position in world coordinates will not change at all during run time...


- ØØ -

---

Ah I get what you are saying now, but I'm not sure if this will get rid of the artifacts.

Quote:

---

Originally Posted by kedaman

Ah I get what you are saying now, but I'm not sure if this will get rid of the artifacts.

---

The camera is not movable at the time, unless you recompile the code...but for the first two tests it looks like it is working. Will get back to that problem if there still is one. But I doubt it.


- ØØ -

Quote:

---

Originally Posted by si_the_geek

I disagree, the issues in the picture above can be caused by that for two "walls" that meet at the corners, as the closest points are the same for both of them.

You should stick to the centre points :)

---

Hardly they will overlapp each other though?

I should have said two walls, or wall/floor, or wall/ceiling. If the closest points of a section of wall and floor meet, you get the issues as shown in the picture on the right (arguably to a lesser degree, but still obvious).

It is hard to say since the camera is not up and runnnig and rotating. But for me right now it looks like Insert sort is SLIGHTLY faster then Shell sort. And since it is faster then I will guess that insert is faster then quick sort too, so then I don't think I care to make a quick sort algo in C# just to test.

Thanks to everyone for participating in this thread..:)

- ØØ -

Quote:

---

Originally Posted by si_the_geek

I should have said two walls, or wall/floor, or wall/ceiling. If the closest points of a section of wall and floor meet, you get the issues as shown in the picture on the right (arguably to a lesser degree, but still obvious).

---

Hmm I can see what you are saying from the picture, but this only happens if you have floors that are behind the wall they are connected to which would mean these walls have no thickness right?

Quote:

---

Originally Posted by NoteMe

It is hard to say since the camera is not up and runnnig and rotating. But for me right now it looks like Insert sort is SLIGHTLY faster then Shell sort. And since it is faster then I will guess that insert is faster then quick sort too, so then I don't think I care to make a quick sort algo in C# just to test.

Thanks to everyone for participating in this thread..:)

- ØØ -

---

I told you ;)

Quote:

---

Originally Posted by kedaman

Hmm I can see what you are saying from the picture, but this only happens if you have floors that are behind the wall they are connected to which would mean these walls have no thickness right?

---

The walls have no tickness. They are thin as a leaf, so there is a lot of points for walls roof and floor that can be at ONE specific coordinate. But if you calculate the midle of each polygon, then that won't happen.


- ØØ -

Quote:

---

Originally Posted by kedaman

I told you ;)

---

No you did not..:D..you changed your mind many times...:D


DoomSharp();
- Will get you married.

Quote:

---

Originally Posted by NoteMe

The walls have no tickness. They are thin as a leaf, so there is a lot of points for walls roof and floor that can be at ONE specific coordinate. But if you calculate the midle of each polygon, then that won't happen.


- ØØ -

---

Ok, but i guess you wouldn't have to if you only had some thickness on your walls, but then again that might complicate wossy's map editor a bit too much ;)

Quote:

---

Originally Posted by NoteMe

No you did not..:D..you changed your mind many times...:D


DoomSharp();
- Will get you married.

---

No I didn't, I just suggested some other alternatives until you actually told me what you were sorting ;)

The thickness is irrelevant, as the closest point will still be the nearest corner - which is the same for both objects (as the wall goes from floor to ceiling).

Quote:

---

DoomSharp();
- Will get you married.

---

To who? :confused:

Quote:

---

Originally Posted by kedaman

Ok, but i guess you wouldn't have to if you only had some thickness on your walls, but then again that might complicate wossy's map editor a bit too much ;)

---

Yeah, billboards are the keyword here. If/when we apply enemies...they will be billboards as well...:)

Quote:

---

Originally Posted by si_the_geek

The thickness is irrelevant, as the closest point will still be the nearest corner - which is the same for both objects (as the wall goes from floor to ceiling).

To who? :confused:

---

Yeah but this time they wont overlap because the floor or ceiling will be in front of the wall, so its no difference which is rendered first.

Quote:

---

Originally Posted by kedaman

No I didn't, I just suggested some other alternatives until you actually told me what you were sorting ;)

---

Boooo, I don't care...I wrote the algo..:)

Quote:

---

Originally Posted by si_the_geek

To who?

---

You will have to wait and see.

- ØØ

Quote:

---

Originally Posted by NoteMe

Boooo, I don't care...I wrote the algo..:)

---

lol.. how many people haven't written the algo already, we should credit him who invented it instead ;)

Quote:

---

You will have to wait and see.

- ØØ

---

I guess I have to beta test it if it works ;)

Quote:

---

Yeah but this time they wont overlap because the floor or ceiling will be in front of the wall, so its no difference which is rendered first.

---

The floor/ceiling in front are fine, the one under/over the wall still has the same closest corner (unless the walls cross the tile borders).

Quote:

---

Originally Posted by si_the_geek

The floor/ceiling in front are fine, the one under/over the wall still has the same closest corner (unless the walls cross the tile borders).

---

You've totally lost me. There are only one floor and ceiling, and theyre connected to the wall, so that its either in front or behind it. If the walls have thickness, they can only be in front of it, given that the wall is front facing which is necessary if its going to be rendered.

float distX = (wPoints[0].X + wPoints[1].X + wPoints[2].X + wPoints[3].X) / 4;
float distZ = (wPoints[0].Z + wPoints[1].Z + wPoints[2].Z + wPoints[3].Z) / 4;
Position = new Vector(distX, distZ, 1.5f);


hehe..but no one noticed that I forgot to change it here too..:D


- ØØ -

Quote:

---

Originally Posted by NoteMe

float distX = (wPoints[0].X + wPoints[1].X + wPoints[2].X + wPoints[3].X) / 4;
float distZ = (wPoints[0].Z + wPoints[1].Z + wPoints[2].Z + wPoints[3].Z) / 4;
Position = new Vector(distX, distZ, 1.5f);


hehe..but no one noticed that I forgot to change it here too..:D


- ØØ -

---

Can't you do any bit shifting in C#?

DoomSharp();
- Will make you look ridiculous.

:D

Yeah you can...what do you think about...the division on four?
How do you do that with floates?

<< 2???


- ØØ -

sorry my bad :blush:

Quote:

---

Originally Posted by kedaman

sorry my bad :blush:

---

Good to see that it is not only me that is tired right now..:)...I can't even get my head around this bounding cricle stuff...:)


- ØØ -

Quote:

---

Originally Posted by kedaman

You've totally lost me. There are only one floor and ceiling, and theyre connected to the wall, so that its either in front or behind it. If the walls have thickness, they can only be in front of it, given that the wall is front facing which is necessary if its going to be rendered.

---

My assumption was that the floor and ceiling were tiles, rather than a single surface for each.

This is based on the artefacts shown in the image - in the closest "problem" two or three floor tiles have been drawn after the wall "in front" of them, and the wall to the left has been drawn afterwards.

I could be wrong of course!!

Quote:

---

Originally Posted by si_the_geek

My assumption was that the floor and ceiling were tiles, rather than a single surface for each.

This is based on the artefacts shown in the image - in the closest "problem" two or three floor tiles have been drawn after the wall "in front" of them, and the wall to the left has been drawn afterwards.

I could be wrong of course!!

---

Yeah I know what you mean, but these walls were billboarded.. anyway I think in this case its best to go with this method.

Anyway

Quote:

---

float distX = (wPoints[0].X + wPoints[1].X + wPoints[2].X + wPoints[3].X) / 4;
float distZ = (wPoints[0].Z + wPoints[1].Z + wPoints[2].Z + wPoints[3].Z) / 4;

---

I was thinking about this again, do you really need the distance other than for sorting? if not then you could leave out the division by 4, because they will still be the same order ;)

Quote:

---

Originally Posted by kedaman

I was thinking about this again, do you really need the distance other than for sorting? if not then you could leave out the division by 4, because they will still be the same order ;)

---

I was actualy thinking about that on the bus on my way home this morning too..:)...I think you are right...

- ØØ -

hehe, great minds :)

Thinking about it again. The position never changes in world coordinates..;)..so I had this function in the constructor..:D..so why even bother to optimize the calculation of the position..:D:D:D:D:


- ØØ -