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.

Quote:

---

Originally Posted by rogster001

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

---

That seems completely wrong to me.

When I made a file and did a command line sort I got

Quote:

---

Originally Posted by sorted.txt

1 3 2 5
1 4 2 6
1 4 3 5
1 6 3 2
1 6 3 5
2 1 3 4
2 4 6 3
2 5 4 1
2 6 5 4
3 5 6 4
4 3 6 1
5 2 6 3
5 3 2 4
5 6 1 2
6 1 5 4

---

Which seems more in line with what you are talking about.

You better triple check this in your original project.

Not quite.

Quote:

---

Originally Posted by rogster001

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!

---

For example, for the following unsorted data:

Code:

---

9 3 5 7
3 8 5 1
4 2 7 5
1 5 3 7
2 4 6 1

---

the sorted data would look like this:

Code:

---

1 2 4 6
1 3 5 7
1 3 5 8
2 4 5 7
3 5 7 9

---

pianorain thats exactly right, whiteflags you forgot to sort each row low to high.

Is there any restriction on what the biggest number we can expect is?

the range of values you can consider defined by the file you have to sort, the final data txt,

Ok good. I will let others have a go before I post my solution.

I have recieved an entry from Zalezog...

i will not be able to test until after the weekend though as i am away, anybody else entering best get submitting their code to me...zalezogs may not run correctly....and someone else could still grab the glory and adulation of millions!

Here is my entry. I guess you bumped the deadline or something.

cheers whiteflags, as far as the deadline goes i did originally say first correct entry received before end date, its because i thought this would be trivial for a lot of members and so could only really do it by time, otherwise it comes down to 'best / most optimal version' or something like that.
I think you might be right though and it should stay open regardless to let everybody keep working at it, then could announce winner as per original rule stated, maybe also announce most optimal. but then i would not really be qualified for that..! Perhaps i could test with a big file to find fastest.
I will await any feedback regarding close date, cheers all.

EDIT: Having reviewed entries so far, contest is still wide open. am sending updates via PM 'where possible' to entrants

From the entries received i think it is right to announce Shakti as the winner, the program submitted was a neat solution using a bitwise operation that worked right out of the box and adhered best to the guidelines.It was also the first received. I will post it up with permission.

so congratulations to Shakti, the glory is yours, be prepared for party invites to come flooding in, Hello magazine and Time magazine on the phone etc etc.

Cheers!

Solution below:

Code:

---

1.#include <iostream>
2.#include <fstream>
3.
4.#define NUM_ROWS 15
5.#define NUM_COLS 4
6.#define BYTE_SHIFT 5
7.
8.
9.// Really really bad name but couldnt be bothered to use something else
10.// Usage is kind of hard to explain but see more info in sort2d function.
11.struct CheckSum
12.{
13.        int originalIndex;
14.        int checkSum;
15.};
16.
17.// Function to use to compare two CheckSum structs in the sorting-function.
18.bool checkSumCompare(const CheckSum a, const CheckSum b)
19.{
20.        return (a.checkSum < b.checkSum);
21.}
22.
23.// Function to use to compare two ints in the sorting function
24.bool intCompare(const int a, const int b)
25.{
26.        return (a < b);
27.}
28.
29.// Templated quicksort that takes a comparer function as well as the usual
30.// array and left and right argument. Maybe not the best implementation but
31.// it serves my needs.
32.template<typename T>
33.void quicksort(T *arr, int left, int right, bool (*comparer)(const T, const T))
34.{
35.        int pivot, leftIdx = left, rightIdx = right;
36.        T temp;
37.        if(right - left > 0)
38.        {
39.                pivot = (left+right)/2;
40.                while(leftIdx <= pivot && rightIdx >= pivot)
41.                {
42.                        while(comparer(arr[leftIdx], arr[pivot]) && leftIdx <= pivot)
43.                                leftIdx++;
44.                        while(comparer(arr[pivot], arr[rightIdx])  && rightIdx >= pivot)
45.                                rightIdx--;
46.                       
47.                        temp = arr[leftIdx];
48.                        arr[leftIdx] = arr[rightIdx];
49.                        arr[rightIdx] = temp;
50.
51.                        leftIdx++;
52.                        rightIdx--;
53.
54.                        if(leftIdx-1 == pivot)
55.                                pivot = rightIdx = rightIdx+1;
56.                        else if(rightIdx+1 == pivot)
57.                                pivot = leftIdx = leftIdx-1;
58.                }
59.
60.                quicksort(arr, left, pivot-1, comparer);
61.                quicksort(arr, pivot+1, right, comparer);
62.        }
63.}
64.
65.// Acutal function where the sorting takes place, each row in arr will
66.// be sorted when function is done, outArr will contain the rows sorted
67.// by column when done.
68.void sort2d(int arr[NUM_ROWS][NUM_COLS], int outArr[NUM_ROWS][NUM_COLS])
69.{
70.        // This is used to hold a number of checksums
71.        // this then gets sorted to find out in what order
72.        // the rows should be and since the CheckSum struct
73.        // has an oldIndex member it is really easy to
74.        // find out what should go where.
75.        CheckSum checkSum[NUM_ROWS];
76.       
77.        // Sort all rows and calculate the checksums
78.        for(int i=0; i<NUM_ROWS; i++)
79.        {
80.                // Sort each row
81.                quicksort(arr[i], 0, NUM_COLS-1, intCompare);
82.
83.                // Calculate checksum for row
84.                checkSum[i].checkSum = 0;
85.                for(int j=0; j<NUM_COLS; j++)
86.                {
87.                        // The checksum is just a simple byte-shift operation of the
88.                        // value of the column in the sorted row.
89.                        // By byteshifting the first value of the row
90.                        // the most we give most priority to the first value
91.                        // and so on.
92.                        checkSum[i].checkSum += (arr[i][j] << (NUM_COLS-j-1)*BYTE_SHIFT);
93.                }
94.
95.                // store the original index for easy finding when constructing
96.                // the final array.
97.                checkSum[i].originalIndex = i;
98.        }
99.
100.
101.        // Sort checkSum array with regards to the check-sums it holds
102.        // This will tell us what order the rows should be to be
103.        // sorted column-wise
104.        quicksort(checkSum, 0, NUM_ROWS-1, checkSumCompare);
105.
106.        // And construct the outArray based on
107.        // the info in checkSum
108.        for(int i=0; i<NUM_ROWS; i++)
109.        {
110.                for(int j=0; j<NUM_COLS; j++)
111.                {
112.                        outArr[i][j] = arr[checkSum[i].originalIndex][j];
113.                }
114.        }
115.}
116.
117.// Read the file....thats it really...
118.bool readFile(int arr[NUM_ROWS][NUM_COLS])
119.{
120.        std::ifstream fin("Final Test Sort Data.txt");
121.        if(!fin)
122.        {
123.                std::cout << "Failed to open file..." << std::endl;
124.                return false;
125.        }
126.        for(unsigned int i=0; i<NUM_ROWS; i++)
127.        {
128.                for(unsigned int j=0; j<NUM_COLS;j++)
129.                {
130.                        if(!(fin >> arr[i][j]))
131.                                return false;
132.                }
133.        }
134.        return true;
135.}
136.
137.int main()
138.{
139.        int arr[NUM_ROWS][NUM_COLS];
140.        int outArr[NUM_ROWS][NUM_COLS];
141.
142.        if(!readFile(arr))
143.                return 0;
144.       
145.        sort2d(arr, outArr);
146.
147.        for(int i=0; i<NUM_ROWS; i++)
148.        {
149.                for(int j=0; j<NUM_COLS; j++)
150.                        std::cout << outArr[i][j] << " ";
151.                std::cout << std::endl;
152.        }
153.}

---

Someone should have implemented a lookup table. Convert each row to a single four digit number, and look up the "row sorted" result for it, then sort a 1D array of integers. :D

Code:

---

int lookup( char four[] )
{
    int table[] = {...};
#define D(x) (four[(x)]-'0')
    return table[ (D(0)*1000) + (D(1)*100) + (D(2)*10) + (D(3)) ];
}

---

Which gives you something like:

Code:

---

char sevenfourtwothree[] = { '7','4','2','3' };
int x = lookup( sevenfourthreetwo ); /* x = 2347 */

---

I didn't happen across this until now, or that probably would have been my entry, in the interest of fun.

Quzah.

Another way. This is with Turbo C, so the file names had to be shortened.

..Input file: FinalIn.txt
Output file: FinalOut.txt

Code:

---


#include <stdio.h>
#include <string.h>
#define MAX 15

void sort(char num[][5], int r, int lo, int hi, int type, int idx[MAX]);
 
int main() {
  int i,r,c,type;
  int idx[MAX];
  char num[MAX][5];
  char line[MAX];
  FILE *fp;

  printf("\n\n\n");
  fp=fopen("FinalIn.txt", "r");
  if(fp==NULL) {
    printf("Error opening file - Correct file name is FinalIn.txt \n");
    return 1;
  }
  r=0;c=0;
  while((fgets(line, sizeof(line), fp)) != NULL) {
    sscanf(line, "%c %c %c %c ", &num[r][c],&num[r][c+1],&num[r][c+2],&num[r][c+3]);
    num[r][4]='\0';
    sort(num, r, 0, 4, 0, idx);  //sort each row
    ++r;
  }
  fclose(fp);
  fp=fopen("FinalOut.txt", "wt");
  putchar('\n');
  sort(num, 0, 0, MAX, 1, idx);  //sort through the index
  for(i=0;i<MAX;i++)
    fprintf(fp,"%s\n", num[idx[i]]);   
  fclose(fp);
  printf("\n\n\t\t\t    press enter when ready\n");
  printf("\n\t\t\t    Output file is FinalOut.txt\n");

  (void) getchar();
  return 0;
}
void sort(char num[][5], int r, int lo, int hi, int type, int idx[MAX]) {
  int i, j;
  char val;
  char *pval;
   
  if(!type) {  //regular insertion sort
    for(i=lo+1;i<hi;i++) { 
      val = num[r][i];
      j = i-1;
      while(num[r][j] > val) {
        num[r][j + 1] = num[r][j];
        --j;
        if(j<0) break;
      } 
      num[r][j+1] = val;
    }
  } 
  else {  //insertion sort of strings, through an index array
    for(i=0;i<MAX;i++)
      idx[i]=i;
    for(i=lo+1;i<hi;i++) { 
      pval = num[idx[i]];
      j = i-1;
      while(strcmp(num[idx[j]], pval) >0) {
        idx[j+1] = idx[j];
        --j;
        if(j<0) break;
      } 
      idx[j+1] = i;
    }
  } 
}

---

Please can you tell me the answer for the following test case?

5 9 1 2
6 8 1 2
7 6 1 2
8 4 1 2