While loop working perfectly in Insertion sort, but For loop is not working as expected in place of-CodePudding

I tried using for loop, but it gives a wrong answer. When I used a while loop in its place the sorting is done as expected. Can someone help me debug?

Note : It doesn't throw an compilation error, just gives a wrong ans when using for loop. And I have tried running on different IDE's and even tried dry running the for loop, but I am unable to understand the problem here.

//While loop
while(j >= 0 && arr[j] > element)
{
    arr[j   1] = arr[j];
    j = j - 1;
}

//For loop
for(; j >= 0; j--)
{
    if(arr[j] > element)
    {
        arr[j   1] = arr[j];
    }
}

Full code if anyone needs

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
    public:
    vector<int> sortArr(vector<int> arr, int n)
    {
        int i, j, element;

        for(i = 1; i < n; i  )
        {
            element = arr[i];
            j = i - 1;

            while(j >= 0 && arr[j] > element)
            {
                arr[j   1] = arr[j];
                j = j - 1;
            }

            /*for(  ; j >= 0 ; j--)
        {
            if(arr[j] > element){
                arr[j   1] = arr[j];
            }    
            
        }*/

            arr[j   1] = element;
        }

        return arr;
    }
};

int main()
{
    vector<int> s(4);
    for(int i = 0; i < 4; i  )
    {
        cin >> s[i];
    }

    Solution ob;
    vector<int> v = ob.sortArr(s, 4);

    for(auto i : v)
    {
        cout << i << ' ';
    }
    cout << endl;

    return 0;
}

CodePudding user response：

Your while and for loops aren't equivalent. With your for loop, j always end up at 0 because there is no equivalence to the && arr[j] > element check. This corrupts the vector content because you'll overwrite index 0.

Equivalent for loop:

for(  ; j >= 0 && arr[j] > element; j--)
{
    arr[j   1] = arr[j];
}

CodePudding user response：

Both are not equivalent, if you look at this:

while (j >= 0 && arr[j] > element)
{
    arr[j   1] = arr[j];
    j = j - 1;
}

It stops as soon as arr[j] > element. But this does not:

for(  ; j >= 0 ; j--)
    {
        if(arr[j] > element){
            arr[j   1] = arr[j];
        }    
        
    }

As it continue to run beyond arr[j] > element. So the equivalent will be:

for(  ; j >= 0 && (arr[j] > element) ; j--)
    {
       arr[j   1] = arr[j];
    }

CodePudding user response：

The loops are written with different logical conditions of break. Look at while:

while (j >= 0 && arr[j] > element)

This loop will break when j is lower than 0 or the arr[j] is lower than element. So if you meet the first element that is equal to/higher than arr[j], the loop will break.

And now let's see the for loop:

for(  ; j >= 0 ; j--)

In this case the only condition is the countdown of value j. But if you find the element equal to / higher than arr[j], meaning this won't be fulfilled:

if(arr[j] > element){

the loop will continue anyways until j isn't lower than 0.

What would repair your code snippet is adding break instruction:

for ( ; j >= 0; j--) {
    if(arr[j] > element) {
        arr[j   1] = arr[j];
    } else {
        break; // the loop will stop, just like the while loop does
    }
}