Public Group

#### Archived

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

# 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.

## 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 on other sites
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 on other sites
Oops! That should have been O(n*log(n)).

--- ganj

##### Share on other sites
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.

Searching:

Hashing
Sequential
Binary

Sorting:

Bubble sort
Selection Sort
Insertion Sort

Merge Sort
Quick Sort
Heap Sort

1. 1
Rutin
26
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 10
• 10
• 9
• 9
• 10
• ### Forum Statistics

• Total Topics
631752
• Total Posts
3002090
×