Sort a 2d Array and keep data intact
Here's a challenge for beginners to have a go at, the
problem is to sort a 2 dimensional array each row low to
high and each column low to high BUT you must maintain the
integrity of the data in each row!
So that means this is similar to sorting words in
alphabetical order. The first element of each row has
priority over the next and so on. (when comparing elements
on different rows in same column position. )
Example:
1 3 4 5
2 3 5 6
1 2 4 6
2 3 4 5
would not become:
1 2 4 5
1 3 4 5
2 3 4 6
2 3 5 6
As some of the column values have shifted out of their original row positions,
making row arrays that werent there before (highlighted in red)
thus the data is scrambled..
The correct sort would be:
1 2 4 6
1 3 4 5
2 3 4 5
2 3 5 6
I had to do this for a display function in a project and
found it quite mindbending to solve, I only just completed
it recently and thought it would make a good challenge to
post up.
I'm not too good at developing sorting algorithms so it took
me a while to figure out a solution. I think i was spending
a lot of time trying absolutely the wrong approach, as soon
as i 'let it go' and started with something else i cracked
it.
The data below is attached as the two files titled 'unsorted
perms' and sorted perms'
They are just the possible permutations of four numbers from six, ignoring number order that makes 15 permutations, and that is what you have to sort.
The sorted version is just a guide so you can see what it should look like when finished.
The unsorted file is for you to practice with as it is
easier to follow what is going on as you work as there is a
complete set of data.
Unsorted:
5 2 6 3
2 6 5 4
4 3 6 1
6 1 5 4
5 3 2 4
2 4 6 3
2 5 4 1
1 4 2 6
1 6 3 2
1 4 3 5
2 1 3 4
3 5 6 4
1 3 2 5
5 6 1 2
1 6 3 5
Sorted:
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 4 5
1 3 4 6
1 3 5 6
1 4 5 6
2 3 4 5
2 3 4 6
2 3 5 6
2 4 5 6
3 4 5 6
You can use this to practice with or just work straight with
the 'Final Test Data.txt', this is a random selection of 15 of the permutations of 4 from 20 numbers, to make it a little more difficult as the complete set is not there.
Rules:
The program should accept the test file 'Final Test Sort
Data.txt'
It should process and output the file to a win32 console,
correctly sorted as described above.
for the purposes of the test assume the array dimensions are
always:
foo[15][4];
so you can hard code that, or make it flexible if you wish,
obviously this is better but not a requirement here.
you dont have to handle it as [n][n] but it has to output in
the table format shown above (15 rows text X 4 columns)
regardless of what you do internally.
Pencil in as stay open one month for completion, Weds 8th December.
The winner is the first person to submit a working program as described. Before the 8thDec.
If anybody thinks this is really easy or knows a solution already then please let others have a go.
It would be interesting to see some optimal versions after the winner is announced.