Ad

Sunday, July 08, 2007

Sorting Two-Dimensional Arrays

Do you know how a 2D array is stored in the memory while the memory is only one-dimensional?

The answer is simple, all the arrays are stored linearly in the memory, be it 2D array or 3D, only the representation is such that to make it easy to reference.

Therefore, if a two-dimensional array has the following elements:

1 2 3
4 5 6
7 8 9

in the memory, it will be like this:

1 2 3 4 5 6 7 8 9

just because memory is linear, and cannot have dimensions. It is the language that represents 2 D arrays as such while in the memory it is always linear.

This property of 2D arrays will be used to sort them, because sorting linear data is much easier.

We don’t need much discussion on this, so here is the example program, please read the comments where all things are elaborated

  // --Sorting Program--
  // -------------------
  // Example Program to sort
  // 2D array using linear
  // representation of the array
  #include<iostream.h>

  #define MAX 3

  void main(void)
  {
   int arr[MAX][MAX];
   int i,j,temp;
   int *arr_ptr;

   for(i=0;i<MAX;i++)
     for(j=0;j<MAX;j++)
       cin>>arr[i][j];

   // we have taken a pointer
   // to the 2D array to
   // represent it linearly

   // C-style type cast
   // is necessary here
   arr_ptr=(int*)arr;

   // sorting is done here.
   // selection sort method of
   // sorting is employed here
   // you can use whichever
   // method you like

   // here MAX*MAX is used 
   // because the no. of elements
   // in the linear representation
   // of the 2D array has that
   // many elements
   for(i=0;i<((MAX*MAX)-1);i++)
     for(j=i+1;j<(MAX*MAX);j++)
       if(*(arr_ptr+i)>*(arr_ptr+j))
       {
        temp=*(arr_ptr+i);
        *(arr_ptr+i)=*(arr_ptr+j);
        *(arr_ptr+j)=temp;
       }
   // sorting is done till here

   cout<<endl;

   for(i=0;i<MAX;i++)
   {
    for(j=0;j<MAX;j++)
    cout<<" "<<arr[i][j];
    cout<<endl;
   }
  }

Good-Bye!

Related Articles:


15 comments:

  1. Just want to say thank you. This helped me a bit.

    ReplyDelete
  2. thanks so much! i hadn't thought of this method at all! this really helps!
    clever!
    keep it up!

    ReplyDelete
  3. Thanks a lot! This is fantastic!

    ReplyDelete
  4. @Chandu

    Thanks for appreciating!

    Enjoy!

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Awesome! Thanks you very much!

    ReplyDelete
  7. @ Alexander,

    It is my pleasure.

    ReplyDelete
  8. Thanks. This post had something that I was looking for.

    ReplyDelete
  9. Anonymous4:35 PM

    thankyou...

    ReplyDelete
  10. Hi Vandana & Anonymous,

    My pleasure!

    ReplyDelete
  11. all i want was a program of two dimensional array without "cin".........please help me!!!!!!!!!!!!!! its hard for me you know. tnx.

    ReplyDelete
  12. Anonymous6:49 PM

    good yar

    ReplyDelete
  13. Probably the best implementation of bubble sort for 2d arrays I have seen...

    ReplyDelete

You are free to comment anything, although you can comment as 'Anonymous' it is strongly recommended that you supply your name. Thank You.

Please don't use abusive language.