Insertion sort implementation in C++ results in multiple errors

Question

This is a console application on CodeBlocks 13.12.

I am getting a variety of errors when I run this Insertion Sort.

Sometimes it prints outrageously large values that weren't in the original array. Or sometimes it runs and sorts the array perfectly fine.

Can anybody please point out what could possibly be wrong? Sorry I'm a noob.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;    

void insertionSort(int arr[], int size);

int main()
{
    int size;
    srand(time(NULL));
    cout << "Specify the size of your array: ";
    cin >> size;
    int theArray[size]; // creates an array of a size the user chooses

    cout << endl << "Your current array: {";

    for (int i = 0; i < size; i++) //prints out the original array
    {
        theArray[i] = rand() % 10000;
        cout << theArray[i];

        if (i != size - 1) // to beautify output
        {
            cout << ", ";
        }
        if (i % 10 == 0 && i != 0)
        {
            cout << endl;
        }
    }
    cout << "}" << endl << endl;

    insertionSort(theArray, size);
}

void insertionSort(int arr[], int size)
{
    int begin = clock(); // are for timing the sort
    for (int i = 0; i < size; i++) //does the sorting
    {
        int j = i + 1;
        int temp = arr[j];

        while (arr[i] > arr[j])
        {
            arr[j] = arr[i];
            arr[i] = temp;
            j--;
            i--;
        }
    }
    int end = clock(); // are for timing the sort

    cout << endl << "Your sorted array is: {";

    for (int i = 0; i < size; i++) // prints out sorted array
    {
        cout << arr[i];
        if (i != size - 1)
        {
            cout << ", ";
        }
        if (i % 10 == 0 && i != 0)
        {
            cout << endl;
        }
    }

    cout << "}" << endl << endl << "Your sort took: " << end - begin << " milliseconds" << endl << endl;
}

Answer 1

As already mentioned by marom in his answer, when i = size - 1 you set j = size and access memory out of bounds, similarly, consider the case where j is set to the smallest element in the array, in that case you reach the left most position of the array by swapping the elements and decrementing, and eventually, i will become negative (since you do not put a bound to check if i becomes less than 0) and so will j and you will be accessing memory out of your bounds again.

Moreover, you are decrementing the value of i as well, which does not make sense, since by decrementing the value of i you are making extra runs for the external for loop.

So, your function shall look something like this ::

for (int i = 0; i < size - 1; i++) //changed the limit of for loop
{
    int j = i + 1;
    int temp = arr[j];

    while ((j > 0) && (arr[j - 1] > arr[j])) //instead of working with the values of i, now we are doing everything with j
    {
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
        j--;
    }
}

Hope this helps!

Answer 2

Additionally to @marom's answer, in your while loop, you don't put limitations neither on i or j, hence you try to access arr[-1], arr[-2] and so on. Also, you go back to the beginning of the sorted array, since you decrement i. Have a look at this code, compiled with g++ 4.8.1 gives no errors. Also, try to use std::swap defined in header <utility> since c++11 or in header <algorithm> until c++11.

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <utility>

using namespace std;    

void insertionSort(int arr[], int size);

int main()
{
    int size;
    srand(time(NULL));
    cout << "Specify the size of your array: ";
    cin >> size;
    int theArray[size]; // creates an array of a size the user chooses

    cout << endl << "Your current array: {";

    for (int i = 0; i < size; i++) //prints out the original array
    {
        theArray[i] = rand() % 10000;
        cout << theArray[i];

        if (i != size - 1) // to beautify output
        {
            cout << ", ";
        }
        if (i % 10 == 0 && i != 0)
        {
            cout << endl;
        }
    }
    cout << "}" << endl << endl;

    insertionSort(theArray, size);
}

void insertionSort(int arr[], int size)
{
    int begin = clock(); // are for timing the sort
    for (int i = 0; i < size - 1; i++) //does the sorting
    {
        int j = i + 1;
        int temp = arr[j];

        while (j > 0 && arr[j] < arr[j - 1])
        {
            // ^^ this ensures that we don't try to access arr[-1]
            swap(arr[j], arr[j-1]); //prefer std functions if they do the job you want
            j--;//we don't go back
        }
    }
    int end = clock(); // are for timing the sort

    cout << endl << "Your sorted array is: {";

    for (int i = 0; i < size; i++) // prints out sorted array
    {
        cout << arr[i];
        if (i != size - 1)
        {
            cout << ", ";
        }
        if (i % 10 == 0 && i != 0)
        {
            cout << endl;
        }
    }

    cout << "}" << endl << endl << "Your sort took: " << end - begin << " milliseconds" << endl << endl;
}

Answer 3

First advice : don't do all your printing or clock measure in your sort function. Keep that for your main program. Your sort function must remain clear and concise with no side effect. Now, i find it better to split the code into 2 simple functions :

First, if arr is assumed already sorted up the index n-1 you want to insert the adequate element of the table at pos offset so that arr will be sorted up to index n:

void insert(int arr[], int n){
 int i=n, temp=arr[n];
 while ( (arr[i-1]>temp) && (i>0) ) 
    {
     arr[i]=arr[i-1];
     i--;
    }
 arr[i]=temp;
}

Now we just have to call our insertion for all offsets in arr except first one:

void insertionSort(int arr[], int size)
{
 for(int n=1; n<size; n++) insert(arr,n);
}

Answer 4

At least this is wrong:

void insertionSort(int arr[], int size)
{
    int begin = clock(); // are for timing the sort
    for (int i = 0; i < size; i++) //does the sorting
    {
        int j = i + 1;

When i is size-1 then j equals size and you get over the bounds of the array (valid values are from 0 to size-1 included). You need to limit your for loop to i < size-1