Sorting 2D Dynamic array of integers , Snake Style

[YoTaMiX]

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

[Ancient Dragon]

use qsort, std::sort(), or some other sort algorithm to sort the array normally then just print the values out in the desired order.

[YoTaMiX]

question : how Qsort will help me? if a 2D array is one big 1D arrray , should i work line by line ?

[Narue]

>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:

#include <stdio.h>
#include <stdlib.h>

#define ROWS 4
#define COLS 4

int cmp ( const void *a, const void *b )
{
  const int *pa = a, *pb = b;

  if ( *pa < *pb )
    return -1;
  else if ( *pa > *pb )
    return +1;
  else
    return 0;
}

int main ( void )
{
  int a[ROWS][COLS];
  int i, j;

  for ( i = 0; i < ROWS; i++ ) {
    for ( j = 0; j < COLS; j++ ) {
      int r = rand() % 100;

      a[i][j] = r;
      printf ( "%d ", r );
    }

    puts ( "" );
  }

  puts ( "" );
  /* Not portable */
  qsort ( a, ROWS * COLS, sizeof ( int ), cmp );

  for ( i = 0; i < ROWS; i++ ) {
    if ( i % 2 == 0 ) {
      for ( j = 0; j < COLS; j++ )
        printf ( "%d ", a[i][j] );
    }
    else {
      for ( j = COLS - 1; j >= 0; j-- )
        printf ( "%d ", a[i][j] );
    }

    puts ( "" );
  }

  return 0;
}

You can do a similar feat of educated type mangling in C++ as well:

#include <iostream>
#include <algorithm>

using namespace std;

const int ROWS = 4;
const int COLS = 4;

int main()
{
  int a[ROWS][COLS];

  for ( int i = 0; i < ROWS; i++ ) {
    for ( int j = 0; j < COLS; j++ ) {
      int r = rand() % 100;

      a[i][j] = r;
      cout<< r <<' ';
    }

    cout<<'\n';
  }

  cout<<'\n';

  /* Not Portable */ {
    int *pa = (int *)a;
    sort ( pa, pa + ( ROWS * COLS ) );
  }

  for ( int i = 0; i < ROWS; i++ ) {
    if ( i % 2 == 0 ) {
      for ( int j = 0; j < COLS; j++ )
        cout<< a[i][j] <<' ';
    }
    else {
      for ( int j = COLS - 1; j >= 0; j-- )
        cout<< a[i][j] <<' ';
    }

    cout<<'\n';
  }
}

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:

#include <stdio.h>
#include <stdlib.h>

#define ROWS 4
#define COLS 4

int cmp ( const void *a, const void *b )
{
  const int *pa = a, *pb = b;

  if ( *pa < *pb )
    return -1;
  else if ( *pa > *pb )
    return +1;
  else
    return 0;
}

void reverse ( int a[] )
{
  int i, j;

  for ( i = 0, j = COLS - 1; i < j; i++, j-- ) {
    int save = a[i];
    a[i] = a[j];
    a[j] = save;
  }
}

int main ( void )
{
  int a[ROWS][COLS];
  int i, j;

  for ( i = 0; i < ROWS; i++ ) {
    for ( j = 0; j < COLS; j++ ) {
      int r = rand() % 100;

      a[i][j] = r;
      printf ( "%d ", r );
    }

    puts ( "" );
  }

  puts ( "" );
  /* Not portable */
  qsort ( a, ROWS * COLS, sizeof ( int ), cmp );

  for ( i = 0; i < ROWS; i++ ) {
    if ( i % 2 != 0 )
      reverse ( a[i] );

    for ( j = 0; j < COLS; j++ )
      printf ( "%d ", a[i][j] );

    puts ( "" );
  }

  return 0;
}

With an easier time of it in C++ because reverse is a standard algorithm:

#include <iostream>
#include <algorithm>

using namespace std;

const int ROWS = 4;
const int COLS = 4;

int main()
{
  int a[ROWS][COLS];

  for ( int i = 0; i < ROWS; i++ ) {
    for ( int j = 0; j < COLS; j++ ) {
      int r = rand() % 100;

      a[i][j] = r;
      cout<< r <<' ';
    }

    cout<<'\n';
  }

  cout<<'\n';

  /* Not Portable */ {
    int *pa = (int *)a;
    sort ( pa, pa + ( ROWS * COLS ) );
  }

  for ( int i = 0; i < ROWS; i++ ) {
    if ( i % 2 != 0 )
      reverse ( a[i], a[i] + COLS );

    for ( int j = 0; j < COLS; j++ )
      cout<< a[i][j] <<' ';

    cout<<'\n';
  }
}

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:

int **a = new int[ROWS * COLS];

But this doesn't because they might not be:

int **a = new int*[ROWS];

for ( int i = 0; i < ROWS; i++ )
  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.

[YoTaMiX]

Hello again ,

I am adding the Code for the Prog .... where the remarks are,
its is where i stuck . thanx again

[Narue]

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:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void ResetArray(int **input,int a_size);
void PrintArray(int **input,int a_size);
void SnakeSort(int **input,int *base,int a_size);

int main(void)
{
  int *base,**user,x,size;

  srand((unsigned)time(NULL));
  printf("enter Dimension\n");
  scanf("%d",&size);
  getchar();

  /* Memory Allocation for 2D Array */
  base = malloc(size * size * sizeof *base);
  user = malloc(size * sizeof *user);
  for (x = 0; x < size; x ++)
    user[x] = &base[x * size];

  ResetArray(user,size);
  PrintArray(user,size);
  printf("\n");

  SnakeSort(user,base,size);
  PrintArray(user,size);

  free(user);
  free(base);

  getchar();
  return 0;
}

void ResetArray(int **input,int a_size)
{
  int i,x;

  for (i = 0; i < a_size; i++)
  {
    for (x = 0; x < a_size; x++)
      input[i][x] = rand() % 100;
  }
}

void PrintArray(int **input,int a_size)
{
  int i,x;

  for (i = 0; i < a_size; i++)
  {
    for (x = 0; x < a_size ; x++)
      printf("%d ",input[i][x]);
    printf("\n");
  }
}

/* Comparison routine for qsort */
static int cmp(const void *a, const void *b)
{
  const int *pa = a,*pb = b;

  if (*pa < *pb)
    return -1;
  else if (*pa > *pb)
    return +1;
  else
    return 0;
}

/* Array reversal for SnakeSort */
static void reverse(int array[],int size)
{
  int i = 0;
  int j = size - 1;

  while (i < j)
  {
    int save = array[i];
    array[i++] = array[j];
    array[j--] = save;
  }
}

void SnakeSort(int **input,int *base,int a_size)
{
  int i;

  /* Sort the entire base */
  qsort(base,a_size * a_size,sizeof *base,cmp);

  /* Reverse every other row */
  for (i = 0; i < a_size; i++)
  {
    if (i % 2 != 0)
      reverse(input[i],a_size);
  }
}

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.

[YoTaMiX]

Thanx , i hope i can use it :-)