LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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


Reply
  Search this Thread
Old 11-11-2006, 08:14 AM   #1
George2
Member
 
Registered: Oct 2003
Posts: 354

Rep: Reputation: 30
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
 
Old 11-11-2006, 03:39 PM   #2
Mara
Moderator
 
Registered: Feb 2002
Location: Grenoble
Distribution: Debian
Posts: 9,696

Rep: Reputation: 232Reputation: 232Reputation: 232
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.
 
Old 11-11-2006, 10:10 PM   #3
George2
Member
 
Registered: Oct 2003
Posts: 354

Original Poster
Rep: Reputation: 30
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
 
Old 11-12-2006, 05:58 AM   #4
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
Keywords to help your search(there are more) sorted from bad to good.
Bubble sort, Insert sort, Quick sort, Heap sort.
 
Old 11-15-2006, 01:35 PM   #5
Mara
Moderator
 
Registered: Feb 2002
Location: Grenoble
Distribution: Debian
Posts: 9,696

Rep: Reputation: 232Reputation: 232Reputation: 232
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...
 
Old 11-19-2006, 03:44 AM   #6
George2
Member
 
Registered: Oct 2003
Posts: 354

Original Poster
Rep: Reputation: 30
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
 
Old 11-19-2006, 03:48 AM   #7
George2
Member
 
Registered: Oct 2003
Posts: 354

Original Poster
Rep: Reputation: 30
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
 
Old 11-19-2006, 02:05 PM   #8
Mara
Moderator
 
Registered: Feb 2002
Location: Grenoble
Distribution: Debian
Posts: 9,696

Rep: Reputation: 232Reputation: 232Reputation: 232
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.
 
Old 11-19-2006, 02:59 PM   #9
jschiwal
LQ Guru
 
Registered: Aug 2001
Location: Fargo, ND
Distribution: SuSE AMD64
Posts: 15,733

Rep: Reputation: 680Reputation: 680Reputation: 680Reputation: 680Reputation: 680Reputation: 680
You guys have me a bit confused.
Quote:
<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]
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.
 
Old 11-19-2006, 06:58 PM   #10
beanxp
LQ Newbie
 
Registered: Nov 2006
Posts: 4

Rep: Reputation: 0
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.
 
Old 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: Reputation: 148Reputation: 148
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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



Similar Threads
Thread Thread Starter Forum Replies Last Post
I need help sorting an array in PHP! socceroos Programming 14 05-09-2006 02:37 AM
building a three dimensional array in vb6 mrobertson Programming 0 08-18-2005 09:12 AM
Bash 2 dimensional array ldp Linux - General 5 07-29-2005 11:29 AM
memory managment problem; higher dimensional array doesn't delete qanopus Programming 5 06-15-2005 04:18 PM
3 dimensional array help leeach Programming 11 06-15-2005 10:46 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

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

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration