🔒 Locked

Fast sorting techniques

Started by JNewt Jul 17, 2003 at 3:30 PM 13 replies 2.1k views

Original Post

Jul 17, 2003 at 3:30 PM

Hi all. I''m working on a 2d isometric game engine and came up against an obvious problem; sorting objects by their y value. I currently have a bubble sort implemented because it''s simple, but I''m looking for something a bit faster. All the algorithm needs to do is go through a linear array sort the y values, ascending order. Thanks in advance.

Thor82

Jul 17, 2003 at 3:38 PM

selection sort is quicker,
but try google for triquicksort i had a VB algorithm, but..i HAD

There aren''''t problems that can''''t be solved with a gun...

theZapper

Jul 17, 2003 at 4:19 PM

Whatever sort you use, you should NEVER use a bubble sort for more than a couple of items.
Search on Google for info on these sorting algorithms: Insertion, merge, quick-sort, selection and Shell.

Or, try your library for this book "Java collections: An introduction to abstract data types, data structures and algorithms" isbn 0-417-89978-x. It contains examples of all the above sorts and more. It also has examples of other stuff like trees, sets, maps, lists, queues and all that rubbish.
It has one major misgiving though, as you may have guessed from the title, it''s in Java.

---
"When I''m in command, every mission''s a suicide mission" - Zapp Branigan

Mermphity

Jul 17, 2003 at 4:30 PM

Like above poster, I recommend quicksort. It, I''ve been told, is the fastest sorting algorithm, except for some very complex ones.

And hey, there''s even a quicksort function in the standard library, and it works great from what I''ve seen. it''s called ''qsort''. Just do ''man qsort'' on Linux or just look it up in some reference. Basically, it takes as arguments the array to sort, number of objects, size of an object, and a function pointer to a function that compares them. Look it up, cuz it''s super-easy to use.

spg

Jul 17, 2003 at 4:40 PM

Quicksort would be my recomendation.

-- Steve --

jermz

Jul 17, 2003 at 4:59 PM

Basic Info on sorting...

It all depends on how many items you''re sorting and what order they are in. Quicksort works well for large lists where the items are randomly distributed. For smaller lists that are mostly in order, insertion sort will work just fine.

RPGGuy

Jul 17, 2003 at 5:12 PM

The Radix sort

http://codercorner.com/RadixSortRevisited.htm

works well sorting large arrays

Oluseyi

526

Oluseyi

Jul 17, 2003 at 5:44 PM

std::sort tends to outperform qsort, and can perform alternate sorts as well.

JNewt

Author

JNewt

Jul 17, 2003 at 8:21 PM

Thanks for all the replies. I''m using Visual Basic and the array shouldn''t include more than few hundred items, so I''m looking for a something that''s relatively easy to implement and not too demanding on resources. The Insertion method looks promising.

Thor82

Jul 18, 2003 at 1:20 PM

i found the file i told you about...if you tell me your email i''ll send you the zip

There aren''''t problems that can''''t be solved with a gun...

nickwinters

Jul 18, 2003 at 4:30 PM

If you''re using quicksort, towards the end, say when each partition has 10 items or less in it, it''s quicker if at that point, you use Selection Sort or Insertion Sort.

Mr Grinch

Jul 22, 2003 at 4:24 PM

Quicksort is not an in-place sorting algorithm, so it uses quite a bit of memory. If that''s not an issue, don''t worry about the rest of my message. Otherwise, heapsort is a pretty good alternative, it''s in-place, so it doesn''t need additional memory (I believe it needs a copy of the array you are sorting). Not sure how big a deal that will be for you though.

darkoneqwe

Jul 22, 2003 at 5:52 PM

I would recommed quick-sort or heap-sort. Depending on type of data you want to sort. If you have a one-time array to sort - use quicksort (man qsort like someone already said

). If you have an array that can get changed (adding new values/removing values) and needs to be sorted all the time you''d need to combine heap sort with some other tricks. Adding value to heap sorted tree takes only log(n) time, sorting takes n log(n).

darkone
Registered Linux User #317188

nickwinters

Jul 22, 2003 at 6:04 PM

quote:
Original post by Mr Grinch
Quicksort is not an in-place sorting algorithm, so it uses quite a bit of memory. If that''s not an issue, don''t worry about the rest of my message. Otherwise, heapsort is a pretty good alternative, it''s in-place, so it doesn''t need additional memory (I believe it needs a copy of the array you are sorting). Not sure how big a deal that will be for you though.

Are you sure you''re not confusing it with merge sort? I''ve always implemented quicksort in place.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.