943,962 Members | Top Members by Rank

Software Development > C > Sorting 2D Dynamic array of integers , Snake Style
Ad:
  • C Discussion Thread
  • Unsolved
  • Views: 6152
  • C RSS
Permalink
Jan 21st, 2006
0

Sorting 2D Dynamic array of integers , Snake Style

Expand Post »
Hello you all!!!
I got an Assignment to sort a Randomized Dynamic 2D Matrix of Integers , Snake style : for Example : biggest number in row 0 , after it follows (beneath it , vividly) the next number :

1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25

(after Sort for example) .
it has to be as less time complex as possible.... and i am stuck. Thanx a lot
Similar Threads
Reputation Points: 10
Solved Threads: 0
Light Poster
YoTaMiX is offline Offline
38 posts
since Jan 2006
Permalink
Jan 21st, 2006
0

Re: Sorting 2D Dynamic array of integers , Snake Style

use qsort, std::sort(), or some other sort algorithm to sort the array normally then just print the values out in the desired order.
Sponsor
Team Colleague
Featured Poster
Reputation Points: 5608
Solved Threads: 2282
Retired and Enjoying Life
Ancient Dragon is offline Offline
21,953 posts
since Aug 2005
Permalink
Jan 21st, 2006
0

Re: Sorting 2D Dynamic array of integers , Snake Style

question : how Qsort will help me? if a 2D array is one big 1D arrray , should i work line by line ?
Reputation Points: 10
Solved Threads: 0
Light Poster
YoTaMiX is offline Offline
38 posts
since Jan 2006
Permalink
Jan 21st, 2006
0

Re: Sorting 2D Dynamic array of integers , Snake Style

>sort a Randomized Dynamic 2D Matrix of Integers
That could be a problem, but first I'll describe how you would do it with a real array.

>how Qsort will help me?
You cheat and give qsort something that it can work with.

>if a 2D array is one big 1D arrray
Yes, and no. In memory, a two-dimensional array is stored contiguously, so yes it is a big one-dimensional array. However, the C (and C++) standard doesn't allow you to portably treat a two-dimensional array as a one-dimensional array. However, you can try it, and it'll probably work:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define ROWS 4
  5. #define COLS 4
  6.  
  7. int cmp ( const void *a, const void *b )
  8. {
  9.   const int *pa = a, *pb = b;
  10.  
  11.   if ( *pa < *pb )
  12.     return -1;
  13.   else if ( *pa > *pb )
  14.     return +1;
  15.   else
  16.     return 0;
  17. }
  18.  
  19. int main ( void )
  20. {
  21.   int a[ROWS][COLS];
  22.   int i, j;
  23.  
  24.   for ( i = 0; i < ROWS; i++ ) {
  25.     for ( j = 0; j < COLS; j++ ) {
  26.       int r = rand() % 100;
  27.  
  28.       a[i][j] = r;
  29.       printf ( "%d ", r );
  30.     }
  31.  
  32.     puts ( "" );
  33.   }
  34.  
  35.   puts ( "" );
  36.   /* Not portable */
  37.   qsort ( a, ROWS * COLS, sizeof ( int ), cmp );
  38.  
  39.   for ( i = 0; i < ROWS; i++ ) {
  40.     if ( i % 2 == 0 ) {
  41.       for ( j = 0; j < COLS; j++ )
  42.         printf ( "%d ", a[i][j] );
  43.     }
  44.     else {
  45.       for ( j = COLS - 1; j >= 0; j-- )
  46.         printf ( "%d ", a[i][j] );
  47.     }
  48.  
  49.     puts ( "" );
  50.   }
  51.  
  52.   return 0;
  53. }
You can do a similar feat of educated type mangling in C++ as well:
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int ROWS = 4;
  7. const int COLS = 4;
  8.  
  9. int main()
  10. {
  11.   int a[ROWS][COLS];
  12.  
  13.   for ( int i = 0; i < ROWS; i++ ) {
  14.     for ( int j = 0; j < COLS; j++ ) {
  15.       int r = rand() % 100;
  16.  
  17.       a[i][j] = r;
  18.       cout<< r <<' ';
  19.     }
  20.  
  21.     cout<<'\n';
  22.   }
  23.  
  24.   cout<<'\n';
  25.  
  26.   /* Not Portable */ {
  27.     int *pa = (int *)a;
  28.     sort ( pa, pa + ( ROWS * COLS ) );
  29.   }
  30.  
  31.   for ( int i = 0; i < ROWS; i++ ) {
  32.     if ( i % 2 == 0 ) {
  33.       for ( int j = 0; j < COLS; j++ )
  34.         cout<< a[i][j] <<' ';
  35.     }
  36.     else {
  37.       for ( int j = COLS - 1; j >= 0; j-- )
  38.         cout<< a[i][j] <<' ';
  39.     }
  40.  
  41.     cout<<'\n';
  42.   }
  43. }
Officially, I don't recommend such tickery, but unofficially, it's probably your most efficient option. Sorting algorithms typically expect only one dimension to work with, so standard solutions don't quite cut it. Your other option would be to devise a custom sorting algorithm that handles a two-dimensional array (not hard, but still takes time), or do an uncomfortable amount of copying. Both of which are likely to be less efficient for both execution and development time.

If you can't just print in the order that's most convenient, then the fastest solution would probably be to reverse every other row:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define ROWS 4
  5. #define COLS 4
  6.  
  7. int cmp ( const void *a, const void *b )
  8. {
  9.   const int *pa = a, *pb = b;
  10.  
  11.   if ( *pa < *pb )
  12.     return -1;
  13.   else if ( *pa > *pb )
  14.     return +1;
  15.   else
  16.     return 0;
  17. }
  18.  
  19. void reverse ( int a[] )
  20. {
  21.   int i, j;
  22.  
  23.   for ( i = 0, j = COLS - 1; i < j; i++, j-- ) {
  24.     int save = a[i];
  25.     a[i] = a[j];
  26.     a[j] = save;
  27.   }
  28. }
  29.  
  30. int main ( void )
  31. {
  32.   int a[ROWS][COLS];
  33.   int i, j;
  34.  
  35.   for ( i = 0; i < ROWS; i++ ) {
  36.     for ( j = 0; j < COLS; j++ ) {
  37.       int r = rand() % 100;
  38.  
  39.       a[i][j] = r;
  40.       printf ( "%d ", r );
  41.     }
  42.  
  43.     puts ( "" );
  44.   }
  45.  
  46.   puts ( "" );
  47.   /* Not portable */
  48.   qsort ( a, ROWS * COLS, sizeof ( int ), cmp );
  49.  
  50.   for ( i = 0; i < ROWS; i++ ) {
  51.     if ( i % 2 != 0 )
  52.       reverse ( a[i] );
  53.  
  54.     for ( j = 0; j < COLS; j++ )
  55.       printf ( "%d ", a[i][j] );
  56.  
  57.     puts ( "" );
  58.   }
  59.  
  60.   return 0;
  61. }
With an easier time of it in C++ because reverse is a standard algorithm:
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int ROWS = 4;
  7. const int COLS = 4;
  8.  
  9. int main()
  10. {
  11.   int a[ROWS][COLS];
  12.  
  13.   for ( int i = 0; i < ROWS; i++ ) {
  14.     for ( int j = 0; j < COLS; j++ ) {
  15.       int r = rand() % 100;
  16.  
  17.       a[i][j] = r;
  18.       cout<< r <<' ';
  19.     }
  20.  
  21.     cout<<'\n';
  22.   }
  23.  
  24.   cout<<'\n';
  25.  
  26.   /* Not Portable */ {
  27.     int *pa = (int *)a;
  28.     sort ( pa, pa + ( ROWS * COLS ) );
  29.   }
  30.  
  31.   for ( int i = 0; i < ROWS; i++ ) {
  32.     if ( i % 2 != 0 )
  33.       reverse ( a[i], a[i] + COLS );
  34.  
  35.     for ( int j = 0; j < COLS; j++ )
  36.       cout<< a[i][j] <<' ';
  37.  
  38.     cout<<'\n';
  39.   }
  40. }
Now, back to the dynamic array part. Depending on how you allocate memory for the array, the above suggestion could work wonderfully (and no longer be non-portable), or nosedive miserably into the realm of pain. In other words, this works because all of the elements are contiguous in memory:
  1. int **a = new int[ROWS * COLS];
But this doesn't because they might not be:
  1. int **a = new int*[ROWS];
  2.  
  3. for ( int i = 0; i < ROWS; i++ )
  4.   a[i] = new int[COLS];
If you allocate memory to your dynamic array with the more common latter example, you're stuck with excessive copying or writing your own custom sorting routine that takes multiple dimensions into account.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004
Permalink
Jan 21st, 2006
0

Re: Sorting 2D Dynamic array of integers , Snake Style

Hello again ,

I am adding the Code for the Prog .... where the remarks are,
its is where i stuck . thanx again
Attached Files
File Type: cpp HW4_2.CPP (1.2 KB, 31 views)
Reputation Points: 10
Solved Threads: 0
Light Poster
YoTaMiX is offline Offline
38 posts
since Jan 2006
Permalink
Jan 21st, 2006
0

Re: Sorting 2D Dynamic array of integers , Snake Style

It's just a matter of taking the complete code that I kindly gave you, and plugging it into your own framework. However, you need to change your allocation method or you can't use qsort. Try to figure out the techniques I used in your updated code before asking. At least that way I won't feel like I'm giving you all of the answers:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. void ResetArray(int **input,int a_size);
  6. void PrintArray(int **input,int a_size);
  7. void SnakeSort(int **input,int *base,int a_size);
  8.  
  9. int main(void)
  10. {
  11.   int *base,**user,x,size;
  12.  
  13.   srand((unsigned)time(NULL));
  14.   printf("enter Dimension\n");
  15.   scanf("%d",&size);
  16.   getchar();
  17.  
  18.   /* Memory Allocation for 2D Array */
  19.   base = malloc(size * size * sizeof *base);
  20.   user = malloc(size * sizeof *user);
  21.   for (x = 0; x < size; x ++)
  22.     user[x] = &base[x * size];
  23.  
  24.   ResetArray(user,size);
  25.   PrintArray(user,size);
  26.   printf("\n");
  27.  
  28.   SnakeSort(user,base,size);
  29.   PrintArray(user,size);
  30.  
  31.   free(user);
  32.   free(base);
  33.  
  34.   getchar();
  35.   return 0;
  36. }
  37.  
  38. void ResetArray(int **input,int a_size)
  39. {
  40.   int i,x;
  41.  
  42.   for (i = 0; i < a_size; i++)
  43.   {
  44.     for (x = 0; x < a_size; x++)
  45.       input[i][x] = rand() % 100;
  46.   }
  47. }
  48.  
  49. void PrintArray(int **input,int a_size)
  50. {
  51.   int i,x;
  52.  
  53.   for (i = 0; i < a_size; i++)
  54.   {
  55.     for (x = 0; x < a_size ; x++)
  56.       printf("%d ",input[i][x]);
  57.     printf("\n");
  58.   }
  59. }
  60.  
  61. /* Comparison routine for qsort */
  62. static int cmp(const void *a, const void *b)
  63. {
  64.   const int *pa = a,*pb = b;
  65.  
  66.   if (*pa < *pb)
  67.     return -1;
  68.   else if (*pa > *pb)
  69.     return +1;
  70.   else
  71.     return 0;
  72. }
  73.  
  74. /* Array reversal for SnakeSort */
  75. static void reverse(int array[],int size)
  76. {
  77.   int i = 0;
  78.   int j = size - 1;
  79.  
  80.   while (i < j)
  81.   {
  82.     int save = array[i];
  83.     array[i++] = array[j];
  84.     array[j--] = save;
  85.   }
  86. }
  87.  
  88. void SnakeSort(int **input,int *base,int a_size)
  89. {
  90.   int i;
  91.  
  92.   /* Sort the entire base */
  93.   qsort(base,a_size * a_size,sizeof *base,cmp);
  94.  
  95.   /* Reverse every other row */
  96.   for (i = 0; i < a_size; i++)
  97.   {
  98.     if (i % 2 != 0)
  99.       reverse(input[i],a_size);
  100.   }
  101. }
And for future reference, post your code in the message rather than attaching a file. Normally I'm not willing to download files just to look at broken code so that I can help you.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004
Permalink
Jan 21st, 2006
0

Re: Sorting 2D Dynamic array of integers , Snake Style

Thanx , i hope i can use it :-)
Reputation Points: 10
Solved Threads: 0
Light Poster
YoTaMiX is offline Offline
38 posts
since Jan 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C Forum Timeline: need help with opengl
Next Thread in C Forum Timeline: How to play sound through stereo speakers





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC