CODEWITHSUNDEEP
c#algorithmsortinginsertion-sort
user6048670
user6048670

Reputation: 2887

What logic error could be leading to a runtime error here?

I have a piece of code that prints the steps of the Insertion Sort algorithm

using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    static void Main(String[] args)
    {
        Console.ReadLine();
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        Func<int[], string> IntArrayToString = (x) => string.Join(" ", Array.ConvertAll(x, k => k.ToString()));
        for(int i = arr.Length - 2, last = arr[arr.Length - 1]; ; --i)
        {
            if(arr[i] > last)
            {
                arr[i + 1] = arr[i]; 
                Console.WriteLine(IntArrayToString(arr));
            }                
            else
            {
                arr[i + 1] = last;
                break;
            }
        }
        Console.WriteLine(IntArrayToString(arr));
    }
}

as per this challenge problem and on one of the 4 test I'm getting a runtime error. Problem is, I can't see what the runtime error or test case is (unless I actually purchase an account on the site). So I must guess-and-check or think through the problem. I already tried adding a 

if(arr.Length < 2)
{
    Console.WriteLine(IntArrayToString(arr));
    return;
}

before the loop but still getting an error.

Upvotes: 0

Views: 77

Answers (1)

Ivan Stoev
Ivan Stoev

Reputation: 205759

Looking at your for loop, it can easily be seen that if there is no value less or equal to the last, the break will never hit, and when i becomes -1, you 'll get IndexOfRangeExpection.

The correct algorithm requires both i and last to be defined outside of the loop. For instance, like this:

int i = arr.Length - 1;
int last = arr[i];
while (--i >= 0 && arr[i] > last)
{
    arr[i + 1] = arr[i];
    Console.WriteLine(IntArrayToString(arr));
}
arr[i + 1] = last;

Of course there are other corner cases like arr.Length < 2, but I think the challenge excludes such possibilities.

Upvotes: 1

Related Questions