Sort an array which is partially sorted

views:

answers:

+2 Q:

Sort an array which is partially sorted

I am trying to sort an array which has properties like

it increases upto some extent then it starts decreasing, then increases and then decreases and so on. Is there any algorithm which can sort this in less then nlog(n) complexity by making use of it being partially ordered?

array example = 14,19,34,56,36,22,20,7,45,56,50,32,31,45......... upto n

Thanks in advance

No, I don't think you can sort it faster, then nlog(n).

Jevgeni Bogatyrjov 2010-10-21 09:27:07

log(n), you mean n*log(n)?

Georg 2010-10-21 09:28:08

+1 A:

You could find the change / partition points, and perform a merge sort between pairs of partitions. This would take advantage of the existing ordering, as normally the merge sort starts with pairs of elements.

Edit Just trying to figure out the complexity here. Merge sort is n log(n), where the log(n) relates to the number of times you have to re-partition. First every pair of elements, then every pair of pairs, etc... until you reach the size of the array. In this case you have n elements with p partitions, where p < n, so I'm guessing the complexity is p log(p), but am open to correction. e.g. merge each pair of paritions, and repeat based on half the number of partitions after the merge.

Shane MacLaughlin 2010-10-21 09:27:15

On similar lines i thought 1) note all points where direction changes. 2)the decreasing sequence we can easily change to increasing by reversing it, will take O(n) for n elements in sequence. 3) now we have array which changes direcrtion only one per element. 4) noting these we can apply merging

peloooo 2010-10-21 09:36:07

@Shane: any pointer to sample implementation of merge sort, efficient re both number of memory moves and extra memory?

Dummy00001 2010-10-21 10:51:20

Googling merge sort comes up with loads of examples. I'd typically be working with arrays, and my preference would be to sort in-place and use iteration rather than recursion. For the question asked, this is very straightforward. Find two adjacent forward and reversed sequences. Merge them into one forward sequence. Repeat for all pairs of sequences in the array. Repeat from the array start until there are no more sequences. Merging in-place simply involves swapping elements from one sequence to the next, where the cursor element on the second sequence is smaller than that of the first.

Shane MacLaughlin 2010-10-21 12:14:15

See Topological sorting

stacker 2010-10-21 09:30:20

Oh this was already mentioned here: http://stackoverflow.com/questions/480640/what-is-the-best-way-to-sort-a-partially-ordered-list

stacker 2010-10-21 09:30:54

+1 A:

Any sequence of numbers will go up and down and up and down again etc unless they are already fully sorted (May start with a down, of course). You could run through the sequence noting the points where it changes direction, then then merge-sort the sequences (reverse reading the backward sequences)

In general the complexity is N log N because we don't know how sorted it is at this point. If it is moderately well sorted, i.e. there are fewer changes of direction, it will take fewer comparisons.

CashCow 2010-10-21 09:31:54

Given that the opening question specifically states the data is partially sorted, I think we need to quantify this in order to move away from n log(n). Simplest way is to count the partitions / changes in direction, which we might call p. In this case the complexity becomes p log(p). If n is proportional to p, e.g. p = n / K where K is constant the complexity is still technically n log(n) although the sort will be faster. If p > n/2 then the pre-condition of the data being partially sorted has not been met.

Shane MacLaughlin 2010-10-21 10:59:03

If we know the nature of its partial sortedness then we can but we were not told this. Given that the spec says no more than the fact that there are regions where it goes up then others where it goes down, we know nothing about its sortedness at all, and any data sequence fits the spec. Therefore either there is no better algorithm generically than O(N log N) or, if you are very clever and come up with one, you will go down in history because it will be a generic sorting algorithm!

CashCow 2010-10-22 11:18:36

If you know for a fact that the data are "almost sorted" and the set size is reasonably small (say an array that can be indexed by a 16-bit integer), then Shell is probably your best bet. Yes, it has a basic time complexity of O(n^2) (which can be reduced by the sequence used for gap sizing to a current best-worst-case of O(n*log^2(n))), but the performance improves with the sortedness of the input set to a best-case of O(n) on an already-sorted set. Using Sedgewick's sequence for gap size will give the best performance on those occasions when the input is not as sorted as you expected it to be.

Stan Rogers 2010-10-21 10:26:58

Strand Sort might be close to what you're looking for. O(n sqrt(n)) in the average case, O(n) best case (list already sorted), O(n^2) worst case (list sorted in reverse order).

Share and enjoy.

Bob Jarvis 2010-10-21 10:33:32

ansaurus

tags:

views:

answers:

Sort an array which is partially sorted

related questions