Sorting 2D Dynamic array of integers , Snake Style

•

What is DaniWeb IT Discussion Community?

You're currently browsing the C section within the Software Development category of DaniWeb, a massive community of 427,744 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 3,854 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.

Join our community!

Please support our C advertiser: Programming Forums

Thread Tools Display Modes

Views: 3449 | Replies: 6

•

Join Date: Jan 2006

Location: Israel

Posts: 37

Reputation: YoTaMiX is an unknown quantity at this point

Rep Power: 3

Solved Threads: 0

YoTaMiX

Offline

Light Poster

Sorting 2D Dynamic array of integers , Snake Style

Jan 21st, 2006

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

•

Join Date: Aug 2005

Location: near St Louis, Missouri, USA

Posts: 11,222

Reputation: Ancient Dragon has much to be proud of

Rep Power: 38

Solved Threads: 935

Ancient Dragon Ancient Dragon is offline

Offline

Most Valuable Poster

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

Jan 21st, 2006

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

•

Join Date: Jan 2006

Location: Israel

Posts: 37

Reputation: YoTaMiX is an unknown quantity at this point

Rep Power: 3

Solved Threads: 0

YoTaMiX

Offline

Light Poster

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

Jan 21st, 2006

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

•

Join Date: Sep 2004

Posts: 6,340

Reputation: Narue has much to be proud of

Rep Power: 29

Solved Threads: 460

Narue

Online

Expert Meanie

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

Jan 21st, 2006

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

Help with Code Tags

(Toggle Plain Text)

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

Help with Code Tags

(Toggle Plain Text)

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

Help with Code Tags

(Toggle Plain Text)

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

Help with Code Tags

(Toggle Plain Text)

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

Help with Code Tags

(Toggle Plain Text)

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

But this doesn't because they might not be:

Help with Code Tags

(Toggle Plain Text)

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.

I'm a programmer. My attitude starts with arrogance, holds steady at condescension, and ends with hostility. Get used to it.

•

Join Date: Jan 2006

Location: Israel

Posts: 37

Reputation: YoTaMiX is an unknown quantity at this point

Rep Power: 3

Solved Threads: 0

YoTaMiX

Offline

Light Poster

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

Jan 21st, 2006

Hello again ,

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

Attached Files

HW4_2.CPP (1.2 KB, 5 views)

•

Join Date: Sep 2004

Posts: 6,340

Reputation: Narue has much to be proud of

Rep Power: 29

Solved Threads: 460

Narue

Online

Expert Meanie

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

Jan 21st, 2006

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:

Help with Code Tags

(Toggle Plain Text)

#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.

I'm a programmer. My attitude starts with arrogance, holds steady at condescension, and ends with hostility. Get used to it.