C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 



Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old November 11th, 2006, 08:08 AM
George2 George2 is offline
Contributing User
Dev Articles Novice (500 - 999 posts)
 
Join Date: May 2006
Posts: 763 George2 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 2 Days 3 h 52 m
Reputation Power: 13
Two dimensional array sorting in C/C++

Hello everyone,


I have a two dimensional array. Currently, I am using the following method to sort,

1. Sort by the first dimension,
2. If the first dimension is equal, then sort by the second dimension.

For example, here is the result of the array I could get,

<result 1>

[1, 2]
[1, 3]
[1, 6]
[2, 4]
[2, 5]
[2, 7]

I want to change it to,

1. Sort by the second dimension,
2. If the second dimension is equal, then sort by the first dimension.

Here is the result I want to get,

<result 2>

[1, 2]
[1, 3]
[2, 4]
[2, 5]
[1, 6]
[2, 7]

I am wondering what is the most efficient way to get the new sorting result (result 2) by the sorting result (result 1) in old method?


thanks in advance,
George

Reply With Quote
  #2  
Old November 11th, 2006, 09:32 AM
ubergeek ubergeek is offline
Contributing User
Dev Articles Novice (500 - 999 posts)
 
Join Date: Jan 2005
Posts: 600 ubergeek User rank is Private First Class (20 - 50 Reputation Level)ubergeek User rank is Private First Class (20 - 50 Reputation Level) 
Time spent in forums: 2 Days 22 h 40 m 27 sec
Reputation Power: 14
Send a message via AIM to ubergeek
Can we see the code you have currently? It seems like it might be a simple matter of changing some indices, but it depends how you implemented the sort.

Reply With Quote
  #3  
Old November 11th, 2006, 11:43 AM
costas costas is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Aug 2006
Posts: 407 costas User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 Days 3 h 25 m 24 sec
Reputation Power: 12
Well, here's an example using bubble sort:

Code:
void sort(int pin[][], int n)
{
	int y,d;
	for(int i=0;i<n-1;i++)
	{
		for(int j=0; j<n-1-i; j++)
		{
			if(pin[j+1][0] < pin[j][0]) // swap values
			{
				y = pin[j][0];
				pin[j][0] = pin[j+1][0];
				pin[j+1][0] = y;
			}
		}
	}
}


Note: put where 0(zero) the number of the column you want to compare e.g.: if it's like this(the table)
|0 1| // columns
[2, 5]
[1, 3]
you should put where zero, 0 if you wanted to sort the array depending on the first column and 1 if you wanted to sort the array depending on the second column!!

well, now if you want to sort it depending on the second column and if it's equal sort it depending on the first column is not very difficult!! You only need to put in the loop(I wrote) an if statement to check if the values are equal and if so do sort differently (depending on the first column)!!


Hope I helped!!

Costas

Last edited by costas : November 11th, 2006 at 11:50 AM.

Reply With Quote
  #4  
Old November 11th, 2006, 10:01 PM
George2 George2 is offline
Contributing User
Dev Articles Novice (500 - 999 posts)
 
Join Date: May 2006
Posts: 763 George2 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 2 Days 3 h 52 m
Reputation Power: 13
Hi ubergeek,


Quote:
Originally Posted by ubergeek
Can we see the code you have currently? It seems like it might be a simple matter of changing some indices, but it depends how you implemented the sort.


I believe there is a sorting algorithm somewhere, actually, what I am doing is to do some simple data mining work -- multi-dimensional sorting. The data is sorted in some physical files, always sorted from left columns at first then sort right columns.

There should be a sorting algorithm implementation, but not available to me. I only have the data. Have I made myself understood enough? :-)

What I want to so is to sort in a different strategy, sorting from right columns at first then sort left columns.


regards,
George

Reply With Quote
  #5  
Old November 11th, 2006, 10:04 PM
George2 George2 is offline
Contributing User
Dev Articles Novice (500 - 999 posts)
 
Join Date: May 2006
Posts: 763 George2 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 2 Days 3 h 52 m
Reputation Power: 13
Thank you Costas,


Quote:
Originally Posted by costas
Well, here's an example using bubble sort:

Code:
void sort(int pin[][], int n)
{
	int y,d;
	for(int i=0;i<n-1;i++)
	{
		for(int j=0; j<n-1-i; j++)
		{
			if(pin[j+1][0] < pin[j][0]) // swap values
			{
				y = pin[j][0];
				pin[j][0] = pin[j+1][0];
				pin[j+1][0] = y;
			}
		}
	}
}


Note: put where 0(zero) the number of the column you want to compare e.g.: if it's like this(the table)
|0 1| // columns
[2, 5]
[1, 3]
you should put where zero, 0 if you wanted to sort the array depending on the first column and 1 if you wanted to sort the array depending on the second column!!

well, now if you want to sort it depending on the second column and if it's equal sort it depending on the first column is not very difficult!! You only need to put in the loop(I wrote) an if statement to check if the values are equal and if so do sort differently (depending on the first column)!!


Hope I helped!!

Costas


Your algorithm works in a brute-force way, I can not utilize the useful information that the two dimensional array is already sorted from left to right. I am wondering how to find a smart/efficient implementation by utilizing the information that the input two dimensional array is already sorted from left to right.

Any ideas?


regards,
George

Reply With Quote
  #6  
Old November 12th, 2006, 05:49 AM
costas costas is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Aug 2006
Posts: 407 costas User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 Days 3 h 25 m 24 sec
Reputation Power: 12
Well, I couldn't understand what you want to say, so I wrote you a code that does what you first mentioned! Here it is:

Code:
#include <iostream>
using namespace std;

int pin[10][2];

void sort(int pin[10][2], int n);

int main()
{
	int x;
	for(int i=0;i<10;i++)  // a for loop to store random numbers in the array
	{
		for(int z=0;z<2;z++)
		{
			pin[i][z] = (z+i+1) + rand()%10;
			cout<<pin[i][z]<<" ";
		}
		cout<<endl;
	}
	sort(pin, 10);  // call to the sort function
	cout<<endl;
	for(int i=0;i<10;i++)  // a for loop to display the results
	{
		for(int z=0;z<2;z++)
		{
			cout<<pin[i][z]<<" ";
		}
		cout<<endl;
	}
	cin>>x;
	return 0;
}

void sort(int pin[10][2], int n)
{
	int y,d;
	for(int i=0;i<n-1;i++)
	{
		for(int j=0; j<n-1-i; j++)
		{
			if(pin[j+1][1] < pin[j][1])  // swap the elements depending on the second row if the next value is smaller
			{
				y = pin[j][1];
				pin[j][1] = pin[j+1][1];
				pin[j+1][1] = y;
				d = pin[j][0];
				pin[j][0] = pin[j+1][0];
				pin[j+1][0] = d;
			}
			else if(pin[j+1][1] == pin[j][1]) // else if the two elements are equal, sort them depending on the first row
			{
				if(pin[j+1][0] < pin[j][0])
				{
					y = pin[j][1];
					pin[j][1] = pin[j+1][1];
					pin[j+1][1] = y;
					d = pin[j][0];
					pin[j][0] = pin[j+1][0];
					pin[j+1][0] = d;
				}
			}
		}
	}
}


Hope I helped!!!


Costas

Reply With Quote
  #7  
Old November 19th, 2006, 01:52 AM
George2 George2 is offline
Contributing User
Dev Articles Novice (500 - 999 posts)
 
Join Date: May 2006
Posts: 763 George2 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 2 Days 3 h 52 m
Reputation Power: 13
Quote:
Originally Posted by costas
Well, I couldn't understand what you want to say, so I wrote you a code that does what you first mentioned! Here it is:

Code:
#include <iostream>
using namespace std;

int pin[10][2];

void sort(int pin[10][2], int n);

int main()
{
	int x;
	for(int i=0;i<10;i++)  // a for loop to store random numbers in the array
	{
		for(int z=0;z<2;z++)
		{
			pin[i][z] = (z+i+1) + rand()%10;
			cout<<pin[i][z]<<" ";
		}
		cout<<endl;
	}
	sort(pin, 10);  // call to the sort function
	cout<<endl;
	for(int i=0;i<10;i++)  // a for loop to display the results
	{
		for(int z=0;z<2;z++)
		{
			cout<<pin[i][z]<<" ";
		}
		cout<<endl;
	}
	cin>>x;
	return 0;
}

void sort(int pin[10][2], int n)
{
	int y,d;
	for(int i=0;i<n-1;i++)
	{
		for(int j=0; j<n-1-i; j++)
		{
			if(pin[j+1][1] < pin[j][1])  // swap the elements depending on the second row if the next value is smaller
			{
				y = pin[j][1];
				pin[j][1] = pin[j+1][1];
				pin[j+1][1] = y;
				d = pin[j][0];
				pin[j][0] = pin[j+1][0];
				pin[j+1][0] = d;
			}
			else if(pin[j+1][1] == pin[j][1]) // else if the two elements are equal, sort them depending on the first row
			{
				if(pin[j+1][0] < pin[j][0])
				{
					y = pin[j][1];
					pin[j][1] = pin[j+1][1];
					pin[j+1][1] = y;
					d = pin[j][0];
					pin[j][0] = pin[j+1][0];
					pin[j+1][0] = d;
				}
			}
		}
	}
}


Hope I helped!!!


Costas



Hi Costas, correct me if I am wrong. Your implementation does not take into account of the given information that the input data is already sorted in a different way -- 1st column then 2nd column. I think if we could utilize the given information, the implementation could be optimized. Agree?


regards,
George

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > Two dimensional array sorting in C/C++


Developer Shed Advertisers and Affiliates


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap