Searching and sorting arrays
Author
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?
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
--- ganj
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.
Google these
Searching:
Hashing
Sequential
Binary
Sorting:
Bubble sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort
Searching:
Hashing
Sequential
Binary
Sorting:
Bubble sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
