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

[NoteMe]

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
- ØØ

[penagate]

Bubble sort.... j/k

Sorting algorithms

[NoteMe]

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:

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


- ØØ -

[penagate]

I see the problem.

Here's more...

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

[NoteMe]

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



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



Thanks
- ØØ -

[penagate]

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

[kedaman]

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.

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

- ØØ -

[kedaman]

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

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.

[NoteMe]

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

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

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.

- ØØ -

[kedaman]

Grrr...give me a break here..

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

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

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.

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

- ØØ -

can you post a screenshot?

[NoteMe]

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.

[NoteMe]

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:

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

[kedaman]

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

[kedaman]

definitively the distance calcuation then

[NoteMe]

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

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);

- ØØ -

[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).

[kedaman]

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

[NoteMe]

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.


- ØØ -

[NoteMe]

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


- ØØ -

[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

[kedaman]

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.

[NoteMe]

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.


- ØØ -

[kedaman]

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?

[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).

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

- ØØ -

[kedaman]

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?

[kedaman]

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

[NoteMe]

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.


- ØØ -

[NoteMe]

I told you

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


DoomSharp();
- Will get you married.

[kedaman]

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

[kedaman]

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


DoomSharp();
- Will get you married.

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

[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).

DoomSharp();
- Will get you married.

To who?

[NoteMe]

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

[kedaman]

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?

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.

[NoteMe]

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

To who?

You will have to wait and see.

- ØØ

[kedaman]

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

You will have to wait and see.

- ØØ

I guess I have to beta test it if it works

[si_the_geek]

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

[kedaman]

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.

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


- ØØ -