ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

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.

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,

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?

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?

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.

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.

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.

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.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.