Sorting Algorithm

[RyanPridgeon]

Can somebody recommend me a good fast sorting algorithm?

I'm just going to be using it to sort some movieclips in a vector by their y property. Any help is appreciated :)

Thanks

[amaterasu]

Bubble sort is pretty quick ( average O(n log(n)) ) and it's easy as hell to implement.

[kiwi-kiwi]

What do you need to sort, how many items are there to be sorted and what language are you using ?

There is a reason for each question

[TropicalPenquin]

Look here. Binary tree is usually the fastest, but only if you are using large amounts of data.

[amaterasu]

oops...its O(n^2) average and worst case :(

But yeah, some more info would help us figure out specifically what you need.

[amaterasu]

and its not quick. at all. me sorting knowledge be rusty.

[RyanPridgeon]

I'm sorting an array of classes by a property, probably going to be about 10 - 50 of them to be sorted.

It's for depth management in my game. Sorting the display objects by their y coordinate so that the depth is correct. (front-top view RPG)

Thankyou for the wiki page. And yeah, I was hoping there was something better than the infamous bubble/shuttle sort :P

It looks like insertion sort is the best for my situation? I'm not entirely sure. Thanks for the help

[kiwi-kiwi]

At 10/22/09 01:33 PM, RyanPridgeon wrote: I'm sorting an array of classes by a property, probably going to be about 10 - 50 of them to be sorted.

It's for depth management in my game. Sorting the display objects by their y coordinate so that the depth is correct. (front-top view RPG)

Thankyou for the wiki page. And yeah, I was hoping there was something better than the infamous bubble/shuttle sort :P

It looks like insertion sort is the best for my situation? I'm not entirely sure. Thanks for the help

For 10-50 items it shouldn't be that big a deal, maybe when the item count gets >40. Also yes insert sort is a good idea to implement in your case because there are going to be a lot of cases when the array is already sorted and that being the best case scenario, it's going to have a O(n) complexity.

But anyway if you're that worried about speed and seeing as you basically sort numbers you could go for the radix sort. It could be a good exercise for you as a programmer to try and do it. If you see you can't do it just go for the insert sort

And best of luck with the development

[Jon-86]

I was gonna recommend A* then I remembered that was a search algorithm. Quicksort is quite a good general one to use. Your best bet would be to generate and extended dataset for testing with that will contain relevant data that you expect to see (if you can) and then run a few algorithms on that and time them.

http://en.wikipedia.org/wiki/Quicksort

[kiwi-kiwi]

At 10/22/09 02:15 PM, Jon-86 wrote:
http://en.wikipedia.org/wiki/Quicksort

Quicksort has n log n complexity in the best case scenario, insert sort has n, I bet there are more frames on average when the depth order doesn't change, so I would go for insert sort on this one, but jon is right, qsort is a pretty popular algorithm that can be applied to any kind of data and might be worth knowing for future projects.

Your best bet would be to generate and extended dataset for testing with that will contain relevant data that you expect to see (if you can) and then run a few algorithms on that and time them.

I would also advise you to do this, it is always a good strategy to test your solutions on a set of random data you expect to see in your application

[henke37]

At 10/22/09 02:15 PM, Jon-86 wrote: I was gonna recommend A* then I remembered that was a search algorithm.

You are even worse off the mark, it's not even a search algorithm, it's a path-finding algorithm.

[Jon-86]

At 10/22/09 03:11 PM, henke37 wrote:

At 10/22/09 02:15 PM, Jon-86 wrote: I was gonna recommend A* then I remembered that was a search algorithm.

You are even worse off the mark, it's not even a search algorithm, it's a path-finding algorithm.

Path finding IS a search problem, A* can be used in many other problems!

[Toast]

At 10/22/09 01:52 PM, kiwi-kiwi wrote: For 10-50 items it shouldn't be that big a deal, maybe when the item count gets >40. Also yes insert sort is a good idea to implement in your case because there are going to be a lot of cases when the array is already sorted and that being the best case scenario, it's going to have a O(n) complexity.

For small lists insertion sort is fine, but since it has a worst case of O(n^2) I wouldn't recommend it if running time is important for you. Merge sort has worst case of O(n lg n) and scales great on bigger lists, but it's kind of an overkill for lists with less than 50 values. Radix sort depends not only on the size of your list, but also on the size of the numbers in your list. The number of times that radix goes through your list is proportional to the amount of significant digits in your values. If all your values are between 0 and 999 it should be ok.

[RyanPridgeon]

I think I'll go with insertion on this one.

Thanks.

[CronoMan]

I'm making a game called fnelda
and by using bubblesort, I needed 18 000 sprites in the same view simultaneously before the framerate dropped below 60fps (where each sprite got sorted by y, so I could draw them in the right order)
And I'm betting you probably don't have that amount of movieclips in your scene
Of course, that's in a completely different language, and the performance is probably a shitload better than AS, but the point is that you probably won't need more than bubblesort. Implementing quicksort, bitsort etc is quite a hassle compared to bubblesort, as you'll need to write binary trees and whatnot and you'll have less time to spend focusing on the content itself

But obviously, this is up to you :P It's fun to write new algorithms anyway, and you'll learn new approaches to common problems

[GustTheASGuy]

At 10/22/09 03:13 PM, Jon-86 wrote: Path finding IS a search problem, A* can be used in many other problems!

Modifying data structures is not one of them. Do you think it's cool to go throwing around names of random algorithms that you suspect would maybe be relevant to the question?

RyanPridgeon: usually standard arrays have a quicksort implementation like in JS/AS that's faster than doing anything manually. For something like depth sorting you can apply an iterative sorter that just swaps some adjacent items each frame.

[Cinjection]

At 10/23/09 05:52 AM, CronoMan wrote: I'm making a game called fnelda
and by using bubblesort, I needed 18 000 sprites in the same view simultaneously before the framerate dropped below 60fps (where each sprite got sorted by y, so I could draw them in the right order)
And I'm betting you probably don't have that amount of movieclips in your scene
Of course, that's in a completely different language, and the performance is probably a shitload better than AS, but the point is that you probably won't need more than bubblesort. Implementing quicksort, bitsort etc is quite a hassle compared to bubblesort, as you'll need to write binary trees and whatnot and you'll have less time to spend focusing on the content itself

But obviously, this is up to you :P It's fun to write new algorithms anyway, and you'll learn new approaches to common problems

Most languages have sort functions already written. All you have to do it figure out how to use them correctly. They are usually really well implemented, so you won't have to worry about performance. It will also save you a lot of time.

[Jon-86]

At 10/23/09 05:53 AM, GustTheASGuy wrote:

At 10/22/09 03:13 PM, Jon-86 wrote: Path finding IS a search problem, A* can be used in many other problems!

Modifying data structures is not one of them. Do you think it's cool to go throwing around names of random algorithms that you suspect would maybe be relevant to the question?

Ah stop being an arse! If you read my initial post you would see I said A* is not suitable here. If you are trying to claim A* is not good for path finding then you've not got a scooby. I'm not throwing names around. I know what your getting at by saying that and I can reassure you that when you take an AI course you will find search and sort algorithms are used quite heavily!

[Glaiel-Gamer]

I was going to recommend SAT, but then I remembered that's a collision detection algorithm.

What language are you using? Most of them have a sort or qsort in their standard library

[GustTheASGuy]

At 10/23/09 02:45 PM, Jon-86 wrote: Ah stop being an arse! If you read my initial post you would see I said A* is not suitable here.

Well great, but then why bring it up at all? It shows you intended to throw in a name without actually thinking about the problem. Like, you were coming up with names of algorithms and only then considering if they're relevant, just so you could post and look like you know anything.

If you are trying to claim A* is not good for path finding then you've not got a scooby.

I'm not talking about A*, I'm talking about you.

I'm not throwing names around. I know what your getting at by saying that and I can reassure you that when you take an AI course you will find search and sort algorithms are used quite heavily!

The topic is sorting. You justify bringing up A* because it's used heavily with AI?

Don't worry about what I know.

[Glaiel-Gamer]

if you want to name-drop algorithms you know to make yourself feel smart, at least post an obscure one like *wikipedias 'algorithms'* the Coppersmith-Winograd algorithm. Oh wait that's not for sorting, i forgot.

[Jon-86]

At 10/23/09 03:36 PM, GustTheASGuy wrote: The topic is sorting. You justify bringing up A* because it's used heavily with AI?

Well yeah because searching can benefit from sorting and vice versa!

[CaptinChu]

Why has nobody yet mentioned merge sort?!

[Glaiel-Gamer]

At 10/23/09 04:01 PM, CaptinChu wrote: Why has nobody yet mentioned merge sort?!

http://en.wikipedia.org/wiki/Sorting_alg orithm#Summaries_of_popular_sorting_algo rithms

there, there's all the useful sort algoruthms

[GustTheASGuy]

At 10/23/09 03:58 PM, Jon-86 wrote: Well yeah because searching can benefit from sorting and vice versa!

Searching is querying various graph structures. Things like ordered data structures can be auxiliarily used in searching, but that doesn't mean the converse somehow applies.
Stop pulling things out of your ass, it's not ..hygenic.

[amaterasu]

At 10/23/09 05:52 AM, CronoMan wrote: I'm making a game called fnelda
and by using bubblesort, I needed 18 000 sprites in the same view simultaneously before the framerate dropped below 60fps (where each sprite got sorted by y, so I could draw them in the right order)
And I'm betting you probably don't have that amount of movieclips in your scene
Of course, that's in a completely different language, and the performance is probably a shitload better than AS, but the point is that you probably won't need more than bubblesort. Implementing quicksort, bitsort etc is quite a hassle compared to bubblesort, as you'll need to write binary trees and whatnot and you'll have less time to spend focusing on the content itself

But obviously, this is up to you :P It's fun to write new algorithms anyway, and you'll learn new approaches to common problems

This man speaks the truth. I rescinded my bubble sort suggestion because I didn't know the amount of objects you need to sort. Just make sure you design your code so that if you do need to upgrade the sort function, its as easy as swapping out a method call.

[Jon-86]

At 10/23/09 04:44 PM, GustTheASGuy wrote: Searching is querying various graph structures. Things like ordered data structures can be auxiliarily used in searching, but that doesn't mean the converse somehow applies.
Stop pulling things out of your ass, it's not ..hygenic.

When sorting really large data sets, an informed sort will get the job done quicker. One method of getting a better heuristic for sorting, is to use a search algorithm to do a bit of probing. If you have access to academic papers through uni or something then look up sort heuristics.

The reason I decided not to mention it is that I dont think it would apply here! Seriously think about it for a second before you think I'm talking crap. Sure it can be a hard thing to implement but theirs nothing wrong with trying. What would be better! A blind sorting algorithm that can only compare say the element before or after it in an array or a sorting algorithm that dose a quick search to find what's out of place before it tries to rearrange the whole array before it gets to the few things that were out of order.

Searching and sorting can be as simple or as complex as you want it to be!

[GustTheASGuy]

At 10/23/09 05:05 PM, Jon-86 wrote: When sorting really large data sets, an informed sort will get the job done quicker. One method of getting a better heuristic for sorting, is to use a search algorithm to do a bit of probing. If you have access to academic papers through uni or something then look up sort heuristics.

Must you be reminded the topic again? Generic sorting. There are no 'heuristics'. The cleverest choice for the depth sorting is an iterative bubble sort. That's all.

I'd certainly be interested on a paper about such a term as 'sort heuristics'. Show me one.

The reason I decided not to mention it is that I dont think it would apply here!

But you did, and it fugging doesn't, at all.

Seriously think about it for a second before you think I'm talking crap. Sure it can be a hard thing to implement but theirs nothing wrong with trying. What would be better! A blind sorting algorithm that can only compare say the element before or after it in an array or a sorting algorithm that dose a quick search to find what's out of place before it tries to rearrange the whole array before it gets to the few things that were out of order.

Son, the one spewing shit is you. To spell it out, you'll have a hard time finding a topic you can tell me anything about.
The point remains is that your justification of randomly mentioning A* because it's a good search algorithm is bullshit.

[Toast]

*popcorn*

[urbn]

At 10/24/09 04:45 AM, GustTheASGuy wrote: The point remains is that your justification of randomly mentioning A* because it's a good search algorithm is bullshit.

But no one else gives a shit?