CODEWITHSUNDEEP
c++optimizationvectorinsertion-sort
user2464351
user2464351

Reputation: 1

Insertion Sort Optimization

I'm trying to practice making some different sort functions and the insertion function that I came up with is giving me some trouble. I can sort lists that are less than 30K fairly quickly. But I have a list of 100K integers and it literally takes 15 minutes for the function to complete the sort. Everything is sorted correctly, but I don't believe it should take that long.

Am I missing something with my code that is making it take so long? Many thanks in advance. 

void Sort::insertion_Sort(vector <int> v)
{
    int vecSize = v.size(); 

    //for loop to advance through the vector
    for (int i=0; i < vecSize; i++)
    {
        //delcare some variables 
        int cursor = i; 
        int inputCursor = i-1; 
        int temp = v[cursor]; 

        //check to see if we are considering only a single element 
        if (cursor > 0)
        {
            //if there is more than 1 element, then we test the following. 
            //1. is the cursor element less than the inputCursor(which 
            //is the previous element) 
            //2. is the input cursor greater than -1
            while (inputCursor > -1 && v[cursor] < v[inputCursor] )
            {

                    //if so, we swap the variables 
                    //then move the cursors back to check 
                    //the previous elment and see if we  need to swap again. 
                    temp = v[cursor];
                    v[cursor] = v[inputCursor];
                    v[inputCursor] = temp;
                    inputCursor--;
                    cursor--; 
            }
        }
    }
}

Upvotes: 0

Views: 5756

Answers (2)

Alessandro Lai
Alessandro Lai

Reputation: 2274

The O(n^2) vs O(n*log(n)) problem, as pointed out by the other answer, is the center of this problem. I would suggest a binary search algorithm, as it is more similar to the insert algorithm, and is simplier to implement. It would look for the point of insertion dividing the already inserted vector in half, and trying to see if the integer to be inserted is greater or not of the integer in the middle. Then, it will try again to split one of the half (the one on the choosen side) and so on, recursively.

I think this is the best approach without starting from scratch.

Upvotes: 0

user3553031
user3553031

Reputation: 6214

Insertion sort is an O(n^2) algorithm. It's slow for large inputs. It's going to take roughly 11 times longer to process a list of 100k items than a list of 30k items. For inputs larger than 20 or so, you should use something like quicksort, which is O(n*log(n)).

Upvotes: 1

Related Questions