Worst Case of Insertion Sort in C#

Question

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( ); 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( ); } 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( The Sorted Array is [ + (i + 1).ToString() + ] + arr[i]); } Console.Write( ); Console.WriteLine( Number 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( The Sorted Array is [ + (i + 1).ToString() + ] + arr[i]); Console.Read(); }

Midhun T P · Answer

Hi Nilesh Try below code - //for worst case: count = 0; for (int i = arr.Length; i > 0; i--) { int j = 1; while (j { 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 { Console.WriteLine(
 The Sorted Array is [ + (i + 1).ToString() + ]  + arr[i]); } Console.Write(
); Console.WriteLine(
Number of Comparision= + count.ToString());

theLizard · Answer

Then all you had to do was static void InsertionSorting() { Console.WriteLine( Insertion Sort:); Console.Write( 
); int [] arr = new int[3]; Random rn = new Random(); for (int i = 0; i { arr[i] = rn.Next(10000); Console.WriteLine( Input Array Element [ +(i + 1).ToString() + ]  + arr[i]); Console.Write( 
); } int count = 0; for (int i = 1; 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 { Console.WriteLine( 
 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(
 The Sorted Array is [ + (i).ToString() + ]  + arr[i-1]); } Console.Write( 
); Console.WriteLine( 
Number of Comparision= + count.ToString());

Midhun T P · Answer

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 Jadav · Answer

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( ); 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( ); } 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( Memory Used by Best Case --> + memoryUsed); Console.Write( ); 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( ); for ( int j = 0; j < 3; j++) { timer.Reset(); timer.Start(); Console.WriteLine( The Best Case time Taken --> + timer.Elapsed.TotalMilliseconds.ToString()); } Console.Write( ); for ( int i = 0; i < 3; i++) { Console.WriteLine( The Ascending Sorted Array is: + arr[i]); } Console.Write( ); Console.WriteLine( Number of Comparision= + count.ToString()); Console.Write( ); Console.Write( ); // 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( The Descending Sorted Array is [ + (i + 1).ToString() + ] + arr[i]); } Console.Write( ); Console.WriteLine( Number 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 Jadav · Answer

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 !

theLizard · Answer

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(
 The Sorted Array is [ + (i).ToString() + ]  + arr[i-1]); }

Nilesh Jadav · Answer

@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 Singh · Answer

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

Dhananjay Kumar · Answer

http://www.codeproject.com/Articles/80546/Comparison-Sorting-Algorithms-in-C-Explained