Modify sorted array or sort the array everytime?

Question

Problem: Given an array of size N, print the sorted sub sets of size K with consecutive elements.

N = 10, K = 4 
8 4 7 5 1 10 3 9 2 6
Output:
4 5 7 8, 1 4 5 7, 1 5 7 10, 1 3 5 10, ...

Approach 1: Sort all the sub sets and print.

Complexity Analysis:

Copy K elements: O((N - K + 1) * (K)) // No of sub sets * size of sub sets

Sort sub set: Using STL, the worst case time to sort a sub set is O(K log K).

Thus, O((N - K + 1) * (K) + (N - K + 1) * (K log K))

Approach 2: From the output sequence, the consecutive sub sets differ by 2 elements. Therefore for the second sub set, Delete the first element and insert the K + 1 th element at the right position.

Complexity Analysis:

Create the first sub set: K

Remove and Insert - linear search (Should this be optimized!): K

Thus, O(K + (N - K + 1) * (K))

I would like to know if the second approach is faster? Is there a significant gain? Is it worthy of not using the STL implementation? Can this be further improved? Is there any other approach? and any suggestions for STL containers for implementation.

For second, approach, you can use binary search, although the insertion and deletion still takes O(k) time — Petar Petrovic
– Petar Petrovic, Commented May 4, 2017 at 7:20

The Quantum Physicist · Accepted Answer · 2017-05-04 06:10:52Z

1

Are duplicates allowed?

If no duplicates are allowed, use std::set, otherwise use std::multiset. set and multiset will keep your elements sorted all the time, and every insertion will go in the right, ordered place. You don't have to worry about when to sort them.

Having everything sorted during insertions is effectively cheaper, because when you have to search, you don't have to compare with all the elements, but only a subset of them.

answered May 4, 2017 at 6:10

The Quantum Physicist

26.6k20 gold badges125 silver badges214 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

DAle · Accepted Answer · 2017-05-04 07:58:32Z

1

Use std::multiset. It would be simple and clean:

vector<int> v = input();
multiset<int> s;
for (int i = 0; i < k; ++i) {
    s.insert(v[i]);
}
print_set(s);

for (int i = 0; i < n-k; ++i) {
    s.erase(s.find(v[i]));
    s.insert(v[i+k]);

    cout << ",";
    print_set(s);
}

You can try it: http://ideone.com/moD3bg

The complexity of all operations with multiset is O(nlogk). But don't remember that complexity of printing all this data is O(n*k).

edited May 4, 2017 at 7:58

answered May 4, 2017 at 7:52

DAle

9,1922 gold badges28 silver badges48 bronze badges

2 Comments

PapaDiHatti Over a year ago

But why you are using find if you can directly pass value to erase member function of multiset

DAle Over a year ago

@Kapil because if duplicates are allowed erase by value could remove more than one number from multiset

PapaDiHatti · Accepted Answer · 2017-05-05 08:09:37Z

0

Just another approach to solve this problem :

  int k=4;
  std::vector<int> v = {8,4,7,5,1,10,3,9,2,6};
  std::multiset<int> ss;
  for(auto itr=v.begin();itr<v.end();itr++)
  {
    size_t remaining(std::distance(itr+k, v.end())); 
    std::cout<<remaining<<std::endl;
    ss.insert(itr,itr+k);
    print_set(ss);
    if(remaining==0)
      break;
    ss.clear();
  }

answered May 5, 2017 at 8:09

PapaDiHatti

1,91321 silver badges29 bronze badges

Collectives™ on Stack Overflow

Modify sorted array or sort the array everytime?

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related