How to get sorted elements from an starting index to a ending index in an array?

Question

Given an array of t integers we need to answer x queries.Each query describes an starting index and a ending index ,we need to print the sorted elements in the sub-array. For Example-
Array={16,9,10,19,2}
for query 1 3 ,the answer would be
9 10 16
for query 2 5,the answer would be
2 9 10 19
Please suggest an optimal solution?Are there any advanced data structures involved?
The number of elements can be upto 10^5 .

Answer 1

Tag each element with it's position:

16 1, 9 2, 10 3, 19 4, 2 5

Sort it:

2 5, 9 2, 10 3, 16 1, 19 4

For each query walk through the result and return the elements which are within the range.

After preprocessing each query takes O(N) work.

Answer 2

Are there any advanced data structures involved?

Nope, not at all. First you obtain the range given by those indexes, then you sort the resulting range. Then you print it. Seems pretty simple!

In fact, it's so simple, I'm going to show you an example:

#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>

template <typename T, size_t N>
size_t len(T (&)[N])
{
   return N;
}


int main()
{
    int array[] = {16,9,10,19,2};

    const int START = 1;  // user input ( 1-based index,)
    const int END   = 3;  // user input (inclusive range)

    assert((START-1) >= 0 && (START <= len(array)));
    assert((END-1)   >= 0 && (END <= len(array)));

    // These two lines do the work.
    // Everything else is just exposition.
    // 
    // First construct a vector from the requested subrange,
    // then sort that resulting vector.
    // 
    std::vector<int> v(array+(START-1), array+END);
    std::sort(std::begin(v), std::end(v));

    // Output the results to console for demo.
    // Uses C++ ranged-for syntax; replace with more
    // verbose equivalent if required, or do something
    // else with `v`.
    // 
    for (auto elm : v) {
       std::cout << elm << ' ';
    }
}

// Output: 9 10 6

Live demo

You could make the code even terser (and possibly more efficient) by copying the subrange into an std::set rather than a std::vector, so sorting happens during insertion rather than after-the-fact. I hardly think either is ever going to be as much as O(n^2), contrary to your claims.

Can you do sufficient preprocessing to share information between individual queries and get your complexity down still further? I don't know. I don't think so.

Answer 3

If I understood your question: Sort it.
You can use any sorting algorithm you want, Wikipedia lists a few.

Depending on which algorithm you choose, you may need extra memory / data structures.

If sorting should come later, copy the array and sort the copy. Makes more sense, than sorting over and over again for every query.