Jump to content
  • Advertisement

Archived

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

Little G

Searching and sorting arrays

This topic is 5551 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
Advertisement
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
Google these

Searching:

Hashing
Sequential
Binary

Sorting:

Bubble sort
Selection Sort
Insertion Sort

Merge Sort
Quick Sort
Heap Sort

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!