Worst Case of Insertion Sort in C#

Nilesh Jadav

I had written Insertion Sort Program in C#, where I got Best Case by sorting the array in ascending form, now I want to get the worst case of the Insertion sort by making that ascending from of sorted output in descending form. How to change my code to do that , Please help me with full code.

I am sharing my code below:

static void InsertionSorting()
{
Console.WriteLine("Insertion Sort:");
Console.Write("\n");
int [] arr = new int[3];
Random rn = new Random();
for (int i = 0; i < 3; i++)
{
arr[i] = rn.Next(10000);
Console.WriteLine("Input Array Element [" +(i + 1).ToString() + "] " + arr[i]);
Console.Write("\n");
}
int count = 0;
for (int i = 1; i < 3; i++)
{
int j = i;
while (j > 0)
{
if (arr[j - 1] > arr[j])
{
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
j--;
}
else
break;
count++;
}
}
for (int i = 0; i < 3; i++)
{
Console.WriteLine("\n The Sorted Array is [" + (i + 1).ToString() + "] " + arr[i]);
}
Console.Write("\n");
Console.WriteLine("\nNumber of Comparision=" + count.ToString());
//for worst case:
Console.Read();
}
static void Main(string[] args)
{
InsertionSorting();
Console.ReadLine();
}
}

**I tried Like this :**

for (int i = arr.Length; i < 0; i--)
{
int j = i;
while (j > 0)
{
if (arr[j - 1] < arr[j])
{
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
j++;
}
else
break;
}
Console.WriteLine("\n The Sorted Array is [" + (i + 1).ToString() + "] " + arr[i]);
Console.Read();
}

9 Replies

Know the answer? Post it — somebody with the same question will find it here.

Midhun Tp10y ago
Accepted answer
Hi Nilesh,
Try below code -
//for worst case:
count = 0;
for (int i = arr.Length; i > 0; i--)
{
int j = 1;
while (j < i)
{
if (arr[j] > arr[j-1])
{
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j++;
}
else
break;
count++;
}

}
for (int i = 0; i < 3; i++)
{
Console.WriteLine("\n The Sorted Array is [" + (i + 1).ToString() + "] " + arr[i]);
}
Console.Write("\n");
Console.WriteLine("\nNumber of Comparision=" + count.ToString());
theLizard10y ago
Then all you had to do was
static void InsertionSorting()
{
Console.WriteLine("Insertion Sort:");
Console.Write("\n");
int [] arr = new int[3];
Random rn = new Random();
for (int i = 0; i < 3; i++)
{
arr[i] = rn.Next(10000);
Console.WriteLine("Input Array Element [" +(i + 1).ToString() + "] " + arr[i]);
Console.Write("\n");
}

int count = 0;
for (int i = 1; i < 3; i++)
{
int j = i;
while (j > 0)
{

if (arr[j - 1] > arr[j])
{
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
j--;
}
else
break;

count++;
}
}
for (int i = 0; i < 3; i++)
{
Console.WriteLine("\n The Sorted Array is [" + (i + 1).ToString() + "] " + arr[i]);

}
Add this code to yours here... You do not need to do what Midhun suggests at all, it is a waste of time since you already have the array sorted in ascending order, all that needs to be done is print the array in reverse order... That is why I gave you the following example...
for (int i = arr.Length; i > 0; i--)
{
Console.WriteLine("\n The Sorted Array is [" + (i).ToString() + "] " + arr[i-1]);
}
Console.Write("\n");
Console.WriteLine("\nNumber of Comparision=" + count.ToString());
Midhun Tp10y ago
Hi Nilesh,
I think I'm not good enough with that scenario. I can't suggest you any better codes for both time & space complexities as I haven't used both cases yet. Hope you get a good solution for both!
Nilesh Jadav10y ago
Thank you Midhun !

Can you further help me ?

I also need the time complexity for both the cases - how much both the loops are taking time to execute ?

Besides I also need the space complexity - how much both the loops are taking memory ?

Do you have any suggestion for that ? I have a code for that - Can you check it is right or wrong ?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Configuration;
using System.Threading;

namespace InsertionSort
{
    class Program
    {
        static void InsertionSorting()
        {
            Console.WriteLine("**Insertion Sort**");
            Console.Write("\n");
            int[] arr = new int[3];
            Random rn = new Random();


            // available processors
            Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(1);
            Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
            Thread.CurrentThread.Priority = ThreadPriority.Highest;

            for (int i = 0; i < 3; i++)
            {
                arr[i] = rn.Next(100);
                Console.WriteLine("Input Array Element [" + (i + 1).ToString() + "] " + arr[i]);
                Console.Write("\n");
            }

            int count = 0;

            for (int i = 1; i < 3; i++)
            {

                int j = i;

                while (j > 0)
                {

                    if (arr[j - 1] > arr[j])
                    {

                        int temp = arr[j - 1];

                        arr[j - 1] = arr[j];

                        arr[j] = temp;

                        j--;

                    }

                    else

                        break;
                    count++;
                }
            }


            Process currentProc = Process.GetCurrentProcess();
            long memoryUsed = currentProc.PagedMemorySize64;
            Console.WriteLine("\nMemory Used by Best Case -->" + memoryUsed);

            Console.Write("\n");


            int result = 0;
            int count2 = 10000;
            int seed = Environment.TickCount;

            Stopwatch timer = new Stopwatch();
            while (timer.ElapsedMilliseconds > 1200)
            {
                result = test(seed, count2);
            }

            timer.Stop();

            Console.Write("\n");
            for (int j = 0; j < 3; j++)
            {
                timer.Reset();
                timer.Start();
                Console.WriteLine("\nThe Best Case time Taken -->" + timer.Elapsed.TotalMilliseconds.ToString());
            }

            Console.Write("\n");


            for (int i = 0; i < 3; i++)
            {
                Console.WriteLine("\n The Ascending Sorted Array is: " + arr[i]);
            }
            Console.Write("\n");
            Console.WriteLine("\nNumber of Comparision=" + count.ToString());
            Console.Write("\n");
            Console.Write("\n");

            // for worst case

           Console.WriteLine("For Worst Case:");

           int count1 = 0;
            for (int i = arr.Length; i > 0; i--)
            {
                int j = 1;
                while (j < i)
                {
                    if (arr[j] > arr[j - 1])
                    {
                        int temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                        j++;

                    }
                    else
                        break;
                    count1++;
                }
            }

            for (int i = 0; i < 3; i++)
            {
                Console.WriteLine("\n The Descending Sorted Array is [" + (i + 1).ToString() + "] " + arr[i]);
            }
            Console.Write("\n");
            Console.WriteLine("\nNumber of Comparision=" + count1.ToString());

        }

        public static int test(int seed, int count2)
        {
            int result = seed;
            for (int i = 0; i < count2; i++)
            {
                result ^= i ^ seed;
            }

            return result;
        }


        static void Main(string[] args)
        {

            InsertionSorting();
            Console.Read();
        }

    }

}
Thank you so much for the help !
Nilesh Jadav10y ago
Hi Lizard !

If you see in debug mode, you will get to know that my worst case is unable to print, might be some mistake in for loop or anywhere else, I can't find it out. For more elaboration I am attaching my console to know you the thing.

Here in the worst case : I want to print the descending form of above array, and besides this I also want to print the No.of comparison , similar you see in best case.

Can you help me to modify the code? or just give me the code, I really need this today !

Thank you !
theLizard10y ago
Your code!? for Best Case is a simple case of lowest number to highest number, if your worst case is simply the reverse of your best, highest to lowest, then the answer to your question is in your code already.
for (int i = arr.Length; i > 0; i--)
{
Console.WriteLine("\n The Sorted Array is [" + (i).ToString() + "] " + arr[i-1]);

}
Nilesh Jadav10y ago
@dhanajay

@Krishna Kumar

Well the case is not as you are defining in your links :

I had a sorted output in ascending form and Now I want to unsort it in descending form.
Krishna Rajput Singh10y ago
Hi Naresh thank you for writing below links helpful for you...:)
http://www.codeproject.com/Articles/80546/Comparison-Sorting-Algorithms-in-C-Explained
http://anh.cs.luc.edu/170/notes/CSharpHtml/sorting.html
Guest User10y ago
http://www.codeproject.com/Articles/80546/Comparison-Sorting-Algorithms-in-C-Explained