1

I am implementing the complex algorithm which part is sorting array of ordered sequences of numbers. The whole algorithm should be nlog(n) complexity, so this part should be same or better but I don't know how to do this.

There is an example. There is an array of sequences:

(0)
(0,1)
(0)
(0,5)
(2,4)
()
(0,5)
()
(2,4)
(1,3,4)

and final sort should be:

()
()
(0)
(0)
(0,1)
(0,5)
(0,5)
(1,3,4)
(2,4)
(2,4)

There are some important notes:

  • sorting is lexicographical
  • sequences are ordered but there is no guarantee for continuousness
  • there are also empty sequences
  • there is a lot of identical sequences
  • sequences are from 0 to hundreds long, no more
  • the array can be 100k long, probably no more
  • final implementation will be in C++ but now it is not probably important

Can you suggest me the best way how to sort it, please? Thanks a lot

2
  • 1
    If your implementation will be in C++ use std::sort and std::lexicographical_compare. This will give you the desired complexity and you can be reasonably sure the code will work. Commented Feb 6, 2011 at 16:38
  • @Blastfurnace Finally I have used std::sort and thank you for pointing out std::lexicographical_compare, I didn't know it.
    – Gaim
    Commented Feb 6, 2011 at 23:32

3 Answers 3

2

Your problem seems similar to radix sort, in this case first sort your sequences by rightmost item (for example 100th item) if no such item exists, set it as min possible value - 1 (for example in the case I can see -1) , then sort this sorted sequence with second rightmost item, and continue this way.

Also if items in sequences all are between 1..k (in this case I can see there are between 1..9) use counting sort to sort them in O(n), if you can use counting sort, the sorting time is O(n) but else the sorting time is O(n log n).

1
  • +1 for radix sort, I know that algorithm but I forgot about it. Maybe it is what I am looking for. I need a time to try it
    – Gaim
    Commented Feb 6, 2011 at 10:33
1

If you use quicksort, then the sort algorithm will be O(n log n). How you have to compare the two items is irrelevant to complexity of the sort itself, and has its own complexity (presumably O(m)).

5
  • Why is it irrelevat? There is a lot of comparisons and also there is a lot of identical sequences, so the comparison will be many times linear. I guess the complexity will be O(m n logn ) and when the m = 100 then it is significant.
    – Gaim
    Commented Feb 6, 2011 at 10:07
  • 1
    Even at m=100, it doesn't even compare to n*log(n) at n=10000. The sort is the dominating algorithm. Your comparison operator is just strcmp(), or a strcmp-like function if the data is stores as integers. How long the "strings" are won't have a significant impact.
    – wuputah
    Commented Feb 6, 2011 at 10:16
  • (+1) for pointing out that the comparison will not affect average complexity. Commented Feb 6, 2011 at 10:22
  • Another way to look at it, is that since sequences will be no more than 100 in size, you can view it as a constant, hence arriving at the running time O(n log n). If you don't view it as a constant (i.e. if you couldn't bound it at 100), then it is in fact wrong to say that the running time is O(n log n), since you can only throw away lower order terms.
    – bassen
    Commented Feb 6, 2011 at 10:30
  • Finally after many tests I found out this is the best way. Thanks a lot
    – Gaim
    Commented Feb 6, 2011 at 23:26
0

If you can integrate GPLv3 code into your project, GNU Sort might be a good place to start. At least, when I ran it on your sample input, I got your sample output, so it's not immediately wrong.

2
  • Is there any description, characteristic and tutorial, please? I cannot find it.
    – Gaim
    Commented Feb 6, 2011 at 10:11
  • @Gaim, it is the standard sort(1) utility included in Linux systems; info sort will give piles of documentation. About the sort itself, "Use a recursive divide-and-conquer algorithm, in the style suggested by Knuth volume 3 (2nd edition), exercise 5.2.4-23. Use the optimization suggested by exercise 5.2.4-10; this requires room for only 1.5*N lines, rather than the usual 2*N lines. Knuth writes that this memory optimization was originally published by D. A. Bell, Comp J. 1 (1958), 75."
    – sarnold
    Commented Feb 6, 2011 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.