Thread: Sort a 2d Array and keep data intact

  1. #1
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472

    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.
    Last edited by rogster001; 11-09-2010 at 04:23 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by rogster001 View Post
    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.

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Not quite.
    Quote Originally Posted by rogster001 View Post
    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
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472

    sort

    pianorain thats exactly right, whiteflags you forgot to sort each row low to high.
    Last edited by rogster001; 11-09-2010 at 04:25 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  5. #5
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Is there any restriction on what the biggest number we can expect is?

  6. #6
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472

    range

    the range of values you can consider defined by the file you have to sort, the final data txt,
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  7. #7
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Ok good. I will let others have a go before I post my solution.

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    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!
    Last edited by rogster001; 11-12-2010 at 06:50 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Here is my entry. I guess you bumped the deadline or something.

  10. #10
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    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
    Last edited by rogster001; 11-15-2010 at 04:48 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  11. #11
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    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.}
    Last edited by rogster001; 12-08-2010 at 05:55 AM. Reason: Permission to post code.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    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.
    Hope is the first step on the road to disappointment.

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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;
        }
      }  
    }

  14. #14
    Registered User
    Join Date
    Jan 2011
    Posts
    18
    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

Popular pages Recent additions subscribe to a feed