Archived

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

Little G

Searching and sorting arrays

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