Share your knowledge at the LQ Wiki.
 LinuxQuestions.org two dimensional array sorting in C/C++
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 11-11-2006, 08:14 AM #1 George2 Member   Registered: Oct 2003 Posts: 354 Rep: 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, [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, [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
 11-11-2006, 03:39 PM #2 Mara Moderator   Registered: Feb 2002 Location: Grenoble Distribution: Debian Posts: 9,696 Rep: If it's not a very big set of data, just re-sort them. On the other hand, the data is partialy sorted in case 2. If you have pointers to all first elements from first column (first 1, first 2 etc) you can notice that first element in the case 2 sorting will be one of them. You just choose from that set, then move the pointer of a choosen element to the next and so on until you reach the last one in each set.
11-11-2006, 10:10 PM   #3
George2
Member

Registered: Oct 2003
Posts: 354

Original Poster
Rep:
Thank you Mara,

Quote:
 Originally Posted by Mara If it's not a very big set of data, just re-sort them. On the other hand, the data is partialy sorted in case 2. If you have pointers to all first elements from first column (first 1, first 2 etc) you can notice that first element in the case 2 sorting will be one of them. You just choose from that set, then move the pointer of a choosen element to the next and so on until you reach the last one in each set.
The number of data is very large. You above algorithm sounds very good. But I am confused about it even after reading twice, for example, in my sample,

how do your algorithm convert the below array

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

to,

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

regards,
George

 11-12-2006, 05:58 AM #4 dmail Member   Registered: Oct 2005 Posts: 970 Rep: Keywords to help your search(there are more) sorted from bad to good. Bubble sort, Insert sort, Quick sort, Heap sort.
 11-15-2006, 01:35 PM #5 Mara Moderator   Registered: Feb 2002 Location: Grenoble Distribution: Debian Posts: 9,696 Rep: Code: ```1st phase 2nd phase 3rd phase 4th phase (pointers) (comparing 1,2 with 2,4) (comparing 1,3 with 2,4) (comparing 1,5 with 2,4) [1, 2] <--- [1, 2] result: [1, 2] result: [1, 2] result: [1, 3] [1, 3] <---- [1, 2] [1, 3] [1, 2] [1, 3] [1, 2] [1, 6] [1, 6] [1, 5] <---- [1, 3] [1, 5] <--- [1, 3] [2, 4] <--- [2, 4] <---- [2, 4] <---- [2, 4] [2, 4] [2, 5] [2, 5] [2, 5] [2, 5] <--- [2, 7] [2, 7] [2, 7] [2, 7]``` and so on...
11-19-2006, 03:44 AM   #6
George2
Member

Registered: Oct 2003
Posts: 354

Original Poster
Rep:
Quote:
 Originally Posted by dmail Keywords to help your search(there are more) sorted from bad to good. Bubble sort, Insert sort, Quick sort, Heap sort.
But your method does not utilize the special character/information of input data, they are already sorted by a 1st column -- 2nd column basis. I think if we could utilize the given information, we could have smarter ways. Any ideas?

regards,
George

11-19-2006, 03:48 AM   #7
George2
Member

Registered: Oct 2003
Posts: 354

Original Poster
Rep:
Quote:
 Originally Posted by Mara Code: ```1st phase 2nd phase 3rd phase 4th phase (pointers) (comparing 1,2 with 2,4) (comparing 1,3 with 2,4) (comparing 1,5 with 2,4) [1, 2] <--- [1, 2] result: [1, 2] result: [1, 2] result: [1, 3] [1, 3] <---- [1, 2] [1, 3] [1, 2] [1, 3] [1, 2] [1, 6] [1, 6] [1, 5] <---- [1, 3] [1, 5] <--- [1, 3] [2, 4] <--- [2, 4] <---- [2, 4] <---- [2, 4] [2, 4] [2, 5] [2, 5] [2, 5] [2, 5] <--- [2, 7] [2, 7] [2, 7] [2, 7]``` and so on...
Hi Mara, I am wondering whether your method works more efficient than traditional quick sort, whose time complexity is n * log (n), what is the time complexity of your solution?

regards,
George

 11-19-2006, 02:05 PM #8 Mara Moderator   Registered: Feb 2002 Location: Grenoble Distribution: Debian Posts: 9,696 Rep: It depends on the data structure used for storing the pointers. If you use a simple list, it's not that well (n2 or so). But if you choose a structure that keep them sorted (and allows fast insertion, let's say in log time) then it's quite good. Edit: from short analysis it looks that it's mlogm (sorting the pointers affects the complexity), if you choose a nlogn sorting algorithm. Oh...and n in that sorting should not be n, but m, in fact. In normal sort n is the number of elements. Here, m is the number of *different* elements in the first column. That's what affects the algotithm most. It may be not effective when n~=m. Edit2: quick sort is not nlogn, not in it's worst case. Average, that's another story. Last edited by Mara; 11-19-2006 at 02:09 PM.
11-19-2006, 02:59 PM   #9
jschiwal
LQ Guru

Registered: Aug 2001
Location: Fargo, ND
Distribution: SuSE AMD64
Posts: 15,733

Rep:
You guys have me a bit confused.
Quote:
 [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, [1, 2] [1, 3] [2, 4] [2, 5] [1, 6] [2, 7]
He said "if the first dimension is equal, then sort by the second", but his example first sorts by the first column and then sorts by the second regardless in its entirety. Also, is he sorting a 2 dimensional array of 2 dimensional vectors.

The example for phase 1 seems fully sorted. Does he want:
initial:
[2, 7]
[1, 3]
[1, 2]
[1, 6]
[2, 5]
[2, 4]
phase 1:
[1, 3]
[1, 2]
[1, 6]
[2, 7]
[2, 5]
[2, 4]
phase 2:
[1, 2]
[1, 3]
[1, 6]
[2, 4]
[2, 5]
[2, 7]

Last edited by jschiwal; 11-19-2006 at 03:01 PM.

11-19-2006, 06:58 PM   #10
beanxp
LQ Newbie

Registered: Nov 2006
Posts: 4

Rep:
I think you just need to use a stable sort to sort by the second dimension. Since your first dimension are alrealy sorted, so the stable sort will not change that order.
The problem is stable sort alogorithms are usually slower than unstable sort, so depend on how many data you have.

Quote:
 Originally Posted by dmail Keywords to help your search(there are more) sorted from bad to good. Bubble sort, Insert sort, Quick sort, Heap sort.

 11-19-2006, 08:29 PM #11 graemef Senior Member   Registered: Nov 2005 Location: Hanoi Distribution: Fedora 13, Ubuntu 10.04 Posts: 2,379 Rep: From what we know... lots of data What we don't know... How often do you want to do this? If it is infrequent then the sort algorithm is not so important If it is very frequent then forget an algorithm and go for a different data structure, such as an index on the data.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post socceroos Programming 14 05-09-2006 02:37 AM mrobertson Programming 0 08-18-2005 09:12 AM ldp Linux - General 5 07-29-2005 11:29 AM qanopus Programming 5 06-15-2005 04:18 PM leeach Programming 11 06-15-2005 10:46 AM

LinuxQuestions.org

All times are GMT -5. The time now is 07:05 AM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -