-1

So I need to sort an vector, and instead of doing things by hand i am using insert and erase.

so far my code is

for (int x = 0; x < arr.size(); x++) {

     for (int y = x; y < arr.size(); y++)
     {

            if ( arr[y] < arr[x])
            {
                arr.insert(arr.begin()+x,arr[y]);
                arr.erase(arr.begin()+y+1);
            }     
     }
}

and yet when it runs I get time outs in my test cases and works for like 3 of them (test cases being 245+ integers of long numbers). I have to use vectors and have to use insertion sort as part of the design (finds minimum swaps to sort but thats cut from here), which i know has bad runtime.

What am I doing wrong here for the compiler to act like this?

muru
  • 4,723
  • 1
  • 34
  • 78
  • Welcome to Stack Overflow. 1) You haven't given us a failing test case (see [here](https://stackoverflow.com/help/mcve)), and 2) *"the compiler"?* – Beta Apr 09 '19 at 23:32
  • Use `std::rotate()` for insertion sort. [See example](https://en.cppreference.com/w/cpp/algorithm/rotate). – Shawn Apr 09 '19 at 23:37
  • Also, see [this implementation](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) of insertion sort, plus other sorting algorithms. – PaulMcKenzie Apr 10 '19 at 00:15

1 Answers1

1

Every time when you call arr.insert or arr.erase you get O(n) complexity. Try to use std::swap (arr[x], arr[y]) instead.

Giorgiy Popov
  • 17
  • 4