It's working but my teacher didn't agreed. Said that my number of iterations will be more. But how??

    void InsertionSort(int arr[], int size)
    {
        for (int i = 1; i < size; i  )
        {
            int flag = 1;
            int val = arr[i];

            for(int j = i-1; j>=0; j--)  //keep swapping till its inserted to its right place
            {
                if(val < arr[j])
                {
                    int temp = arr[j]; 
                    arr[j] = val;
                    arr[i] = temp;
                    i--;  //decrementing i so we keep going left until the condition is false
                    flag = 0;
                }
            if(flag) break; // optimised best case, so inner loop doesn't run for sorted part.
            }
        }
    
    }

CodePudding user response：

Either at least change this code snippet

if(val < arr[j])
{
    int temp = arr[j]; 
    arr[j] = val;
    arr[i] = temp;
    i--;  //decrementing i so we keep going left until the condition is false
    flag = 0;
}

the following way

if(val < arr[j])
{
    int temp = arr[j]; 
    arr[j] = val;
    arr[j 1] = temp;
    flag = 0;
}

Or change your teacher.:)

In fact your function works but it is clumsy due to decreasing the variable i in the inner loop that leads to repeating iterations of the outer loop for the same value of i.

Consider for example an array that starts with elements { 2, 1, ... }. In the first iteration of the outer loop i is initialized by 1. Within the inner loop these two first elements will be swapped and i will be decremented and becomes equal tp 0. Then in the third expression of the outer for loop i will be incremented and will be equal to 1 anew. So the loop will repeat its iteration for the same value of the variable i.

If to use swapping of adjacent elements in the array as you are doing then the function can be written simpler without using the variable flag. Pay attention to that the number of elements in the array should have the type size_t.

Here is a demonstrative program

#include <iostream>
#include <utility>

void InsertionSort( int arr[], size_t size )
{
    for ( size_t i = 1; i < size; i   )
    {
        for( size_t j = i; j != 0 && arr[j] < arr[j-1]; j--)
        {
            std::swap( arr[j], arr[j-1] );
        }
    }
}
    
int main() 
{
    int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    
    InsertionSort( a, sizeof( a ) / sizeof( *a ) );
    
    for ( const auto &item : a )
    {
        std::cout << item << ' ';
    }
    
    std::cout << '\n';
    
    return 0;
}

The program output is

1 2 3 4 5 6 7 8 9