CODEWITHSUNDEEP
c++loopssortinginsertion-sort
At-U
At-U

Reputation: 17

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

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;
}

Upvotes: 1

Views: 575

Answers (3)

Julien BERNARD
Julien BERNARD

Reputation: 701

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];
}

Upvotes: 4

Krzysztof Buczak
Krzysztof Buczak

Reputation: 125

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
    }
}

Upvotes: 1

foragerDev
foragerDev

Reputation: 1409

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];
    }

Upvotes: 3

Related Questions