Partially sorting an array

Question

Partial sorting can be done with std::partial_sort.

Partial sorting means

5 7 4 2 8 6 1 9 0 3

after partial sorting for 3 elements

0 1 2 7 8 6 5 9 4 3

http://en.cppreference.com/w/cpp/algorithm/partial_sort.

But it is not best when some elements would be already sorted.

Is there other such function which could do so and take advantage of partially sorted array.

Have a look at this, http://stackoverflow.com/questions/3985948/sort-an-array-which-is-partially-sorted — , Jul 03 '12 at 18:40
"*But it is not best when some elements would be already sorted.*" On what do you base this statement? — ildjarn, Jul 03 '12 at 18:40
actually i am applying that i a code and it is getting time limit exceeded. — user1484638, Jul 03 '12 at 18:45
What is the application for your partial sort? Would a heap data structure be a better fit? — jxh, Jul 03 '12 at 18:54
i have to partially sort an array repeatedly and sometimes add an element to the end of the array and then again partially sort — user1484638, Jul 03 '12 at 18:58
partial sorting means sort an array only to a particular limit — user1484638, Jul 03 '12 at 19:01
I would suggest adapting the [streaming median](http://stackoverflow.com/questions/10930732/c-efficiently-calculating-a-running-median) algorithm to track your `k` smallest elements. — jxh, Jul 03 '12 at 19:04
possible duplicate of [partially sorting an array in which some numbers are already sorted](http://stackoverflow.com/questions/11310991/partially-sorting-an-array-in-which-some-numbers-are-already-sorted) — Blastfurnace, Jul 03 '12 at 20:29

score 1 · Answer 1 · edited May 23 '17 at 12:12

You can use an adaptation of the streaming median algorithm to track the k smallest terms of a set of terms. You can use std::priority_queue for your min and max heaps.

The algorithm would work like this:

The max heap is used to hold the k smallest terms
The min heap is used to hold all the other terms
For every term to be tracked, decide which heap it should be added to, and add it there
- If the size of the max heap is smaller than k add it there, else
- if the term is smaller than the top of the max heap, add it there, else
- add the term to the min heap
If the top of the max heap has more than k terms, pop off the top term, and push it into the min heap

If you need your terms sorted, you can pop them off the max heap in descending order, placing them in a array in reverse order, leaving you with a sorted array. If you passed in the container to the max heap's constructor, you can copy the container, and sort it.

The std::priority_queue is a max heap by default. To make it a min heap, you modify some of the template parameters.

typedef std::priority_queue<int> MaxHeap;
typedef std::priority_queue
    <
        int,
        std::priority_queue<int>::container_type,
        std::greater<int>
    > MinHeap;

Partially sorting an array

1 Answers1