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

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.

Thank you Mara,


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

Keywords to help your search(there are more) sorted from bad to good.
Bubble sort, Insert sort, Quick sort, Heap sort.

and so on...

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

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

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

You guys have me a bit confused.
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]

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.

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.