Archived

This topic is now archived and is closed to further replies.

Searching and sorting arrays

This topic is 5335 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What is the best way to go about this? I''m writing a program to work out how many possible unique positions there are on a naughts and crosses board. I was going to store all the unique positions in an array, but I can''t really work them very well. Could anyone help?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quick Sort''s seem to be all the rage, but i prefer to use a Heap Sort. They are both O(n*log()n) but the Heap Sort is a little slower. It is simple a simple algorithm to implement, and i personally think it is quite elegant. If you are interested in using the Heap Sort respond back if you want some more details.

--- ganj

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Oops! That should have been O(n*log(n)).

--- ganj

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Little G
What is the best way to go about this? I''m writing a program to work out how many possible unique positions there are on a naughts and crosses board. I was going to store all the unique positions in an array, but I can''t really work them very well. Could anyone help?


The search space for naughts and crosses is comparatively tiny - fewer than 20K possible board-layouts, of which less than a third are legally reachable during a game. Find a good way to encode a board in a single integer (hint: think of it as a number in base-3) and use it to index a single array. No sorting or searching necessary.

Playing all possible games takes my computer only about a tenth of a second. This obviously isn''t a workable strategy for (e.g.) chess, but for naughts and crosses, no problem.

Share this post


Link to post
Share on other sites