Hackerrank Insertion Sort Algorithm 1 (creating duplicates to show shifting)

Question

During an interview, I was given this Hackerrank question to solve within 15 minutes but at that time I was interested in solving this without performance in my mind. I know a similar question has been asked Hackerrank Insertion Sort - Java and probably a lot in CR.

Problem Statement

Given a sorted list with an unsorted number e in the rightmost cell, can you write some simple code to insert into the array so that it remains sorted?

Print the array every time a value is shifted in the array until the array is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.

Guideline: You can copy the value of to a variable and consider its cell "empty". Since this leaves an extra cell empty on the right, you can shift everything over until can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace it with .

Input Format

There will be two lines of input:

• Size - the size of the array
• Arr - the unsorted array of integers

Output Format

On each line, output the entire array every time an item is shifted in it.

Constraints

• 1 ≤ Size ≤ 1000
• -10000 ≤ e ≤ 1000, e E Arr

Sample Input

5
2 4 6 8 3

Sample Output

2 4 6 8 8 
2 4 6 6 8 
2 4 4 6 8 
2 3 4 6 8

---

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    public static void printArray(int[] array)
    {
        var b = array.Select((x) => Convert.ToString(x) + " ").Cast<string>();
        Console.WriteLine(String.Concat(b));
    }

    public static void insertionSort(int[] unsortedArray)
    {
        int unsortedElement = unsortedArray.ElementAt(unsortedArray.Count() - 1);
        int i = unsortedArray.Length - 1;
        while (i != -1)
        {
            if (i - 1 != -1)
            {
                if (unsortedArray[i - 1] > unsortedElement)
                {
                    unsortedArray[i] = unsortedArray[i - 1];
                    printArray(unsortedArray);
                }
                else
                {
                    unsortedArray[i] = unsortedElement;
                    printArray(unsortedArray);
                    break;
                }
            }
            else
            {
                unsortedArray[i] = unsortedElement;
                printArray(unsortedArray);
                break;
            }
            i--;
        }
    }
}

Any thoughts on performance, style or shortened code length?

Answer 1

There's a lot of chaos. Let's clean this up.

---

Issue 1 - Printing

public static void printArray(int[] array)
{
    var b = array.Select((x) => Convert.ToString(x) + " ").Cast<string>();
    Console.WriteLine(String.Concat(b));
}

A lot of code to just concatenate a string. This could be a single line if you used the string.Join method. There is no need to cast or convert anything.

public static void Print(this IEnumerable<int> values, string separator = " ")
{
    Console.WriteLine(string.Join(separator, values));
}

Additionaly I made it an extension that is able to print any collection of ints and you can specify the separator which is by default a single space.

The name is fixed as well to match the PascalCase for public members.

---

Issue 2 - Separation of concerns

The sorting method needs to be optimized and made a little bit more generic. It also shoudn't print anything. Its only job should be sorting.

int unsortedElement = unsortedArray.ElementAt(unsortedArray.Count() - 1);

You use linq's ElementAt, why not the Last extension?

The while loop is huge and the printing along the way makes it hard to maintain and to read. We turn it into an extension that returns each partial result and of course we remove the printing.

There is another thing I don't like about the original solution. Most of the time it's not such a good idea to modify the original array. So I make a copy of it and sort the copy. The while loop can be turned into a for loop that already supports an index which is easier to handle then with a while. We start looping at the nextToLast element backwards.

The final result is:

public static IEnumerable<int[]> InsertionSort(this IEnumerable<int> values)
{
    var copy = values.ToArray();
    var last = values.Last();
    var nextToLast = copy.Count() - 2;

    for (var i = nextToLast; i >= 0; i--)
    {
        if (copy[i] > last)
        {
            copy[i + 1] = copy[i];
            yield return copy;
        }
        else
        {
            copy[i + 1] = last;
            yield return copy;
            yield break;
        }                   
    }

    // This sets the last element at 0 if it didn't fit anywhere else.
    copy[0] = last;
    yield return copy;
}

Usage

Now we can easily combine both extensions to sort the array and print each step of the insertion sort:

var nums = new[] { 2, 4, 6, 8, 9 };
foreach (var step in nums.InsertionSort())
{
    step.Print();
}

Answer 2

A few points specifically for C#.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    // Method name should be in Pascal case.
    public static void PrintArray(int[] array)
    {
        // If it is known that x is an int, x.ToString() is more readable.
        // Also, rather than calling it 'b', you could give a more readable name.
        var strArray = array.Select((x) => x.ToString() + " ").Cast<string>();
        Console.WriteLine(String.Concat(strArray));
    }

    public static void InsertionSort(int[] unsortedArray)
    {
        // Why use Count() and Length in two lines?
        // You could choose the one you prefer and use it everywhere.
        // Also, if you are using var in PrintArray, you should be consistent in its use.
        var unsortedElement = unsortedArray[unsortedArray.Length];
        var i = unsortedArray.Length - 1;
        // I would prefer to keep it i >= 0, as it defines a valid range, rather than a single point. 
        // There is no real difference, but it is more resilient against mistakes like having i-- statements twice.
        while (i >= 0)
        {
            // As pointed by others, i != 0 would be more readable.
            if (i > 0)
            {
                // Shift the element to right if it is bigger than unsorted element.
                if (unsortedArray[i - 1] > unsortedElement)
                {
                    unsortedArray[i] = unsortedArray[i - 1];
                    PrintArray(unsortedArray);
                }
                // Insert the element if the element at i - 1 is smaller or EQUAL to it.
                else
                {
                    unsortedArray[i] = unsortedElement;
                    PrintArray(unsortedArray);

                    break;
                }
            }
            // I prefer to keep a comment with else statements.
            // When i = 0, i.e. for the first element.
            else
            {
                unsortedArray[i] = unsortedElement;
                PrintArray(unsortedArray);

                break;
            }

            i--;
        }
    }
}

Answer 3

Can use a for for the counter and eliminate a lot of the counters

public static void insertionSort(int[] unsortedArray)
{
    int lastIndex = unsortedArray.Length - 1;
    int unsortedElement = unsortedArray.[lastIndex ];
    for (int i = lastIndex; i >= 0; i--)
    {
        if (i == 0)
        {
            unsortedArray[i] = unsortedElement;
            printArray(unsortedArray);
        }
        else if(unsortedArray[i - 1] > unsortedElement)
        {        
            unsortedArray[i] = unsortedArray[i - 1];
            printArray(unsortedArray);
        }
        else
        {
            unsortedArray[i] = unsortedElement;
            printArray(unsortedArray);
            break;
        }
    }
}