We have different sorting algorithms that we can use when we want to sort lists of elements. Insertion sort is one of the simplest algorithms that we can use to achieve our goal. In this article, we learn how insertion sort works, implement the algorithm in C#, and analyze its time and space complexity.\u00a0<\/p>\n
Let’s start.\u00a0<\/p>\n
As the name suggests, insertion sort is an algorithm that sorts a list of elements by taking each element and adding it to the correct position in the list. The algorithm iterates through the list until the array is sorted.\u00a0<\/p>\n
To understand how insertion sort works, let’s use the analogy of a card player who wants to sort some playing cards.<\/p>\n
The player starts with an empty left hand with all the cards on the table. The empty hand in this case symbolizes an empty array that stores the sorted values.<\/p>\n
Then, the player takes one card at a time and places it in the correct position in the left hand. When finding the correct position to place the new card, the player compares the card with the sorted ones in the hand from right to left.\u00a0<\/p>\n
Let’s take a deep dive and have and learn how insertion sort works.\u00a0<\/p>\n
To illustrate how the insertion sort algorithm works, let’s assume we intend to sort this array:<\/p>\n
Assuming 86 is a sorted list of the first item, we are going to compare 86 with 13. Since 13 is less than 86, we switch their positions and the array becomes:<\/p>\n 86 is greater than 60 so we switch their positions and the array becomes:<\/p>\n 86 is greater than 46, hence we shift 86 to the right:<\/p>\n 60 is greater than 46 while 46 is less than 13, so we shift 60 to the right:\u00a0<\/p>\n 86 is greater than 73 and 73 is greater than 60, so we are going to shift 86 to the right:<\/p>\n 86 is greater than 52 so we shift it to the right:<\/p>\n 73 is greater than 52 so we shift it to the right:<\/p>\n 52 is less than 60 while it’s greater than 46, hence we switch 52 and 60 to complete the sorting process:\u00a0<\/p>\n In summary, we can see that insertion sort uses this working principle:<\/p>\n We can implement the insertion sort algorithm recursively or through an imperative approach.\u00a0<\/p>\n Let’s start with the imperative approach.<\/p>\n We are going to define a method We have to assume that the array is logically divided into two segments with the left segment holding sorted elements while the right segment holding unsorted array elements.\u00a0<\/p>\n For each pass of the outer loop, the current element This process is done iteratively until the array is sorted.\u00a0<\/p>\n Finally, we can verify that the We are going to define a method We start by checking whether we are attempting to sort an array that contains a single element as our base case here:\u00a0<\/p>\n If the base-case scenario is not true, To hold the value of the last element in the sorted subarray ( Next, we are going to iterate through the array while comparing Finally, we can verify that the As we’ve seen in the implementation<\/a> section, the insertion sort algorithm sorts all the elements in place. Therefore, the space complexity of insertion sort is O(1)<\/strong>.\u00a0<\/p>\n Insertion sort encounters the best-case time complexity scenario when we attempt to sort an array that is already sorted. In this case, the algorithm is going to compare each array element to its predecessor. Assuming the size of the array is N, the algorithm will take N steps to sort the array.\u00a0<\/p>\n Therefore, the best-case time complexity of insertion sort is O(N)<\/strong>.\u00a0<\/p>\n When insertion sort encounters random array elements it encounters an average-case time complexity scenario. The algorithm compares each array element to its predecessor and finding the correct position to place elements would take O(N2<\/sup>)<\/strong>.\u00a0<\/p>\n This scenario occurs when insertion sort encounters a reversed list. The algorithm inserts every array element at the beginning of the sorted subarray, which makes it have a time complexity of\u00a0 O(N2<\/sup>).<\/strong><\/p>\n To start with, it is simple to learn and use, which makes it easy to implement.\u00a0<\/p>\n Besides being simple to implement, insertion sort is effective when used in memory-intensive applications as it does not require a lot of additional memory.\u00a0<\/p>\n Insertion sort maintains the relative order of the array elements in case it encounters two similar values (stable), unlike quicksort<\/a>, which is unstable.\u00a0<\/p>\n We have learned that insertion sort has an average-case<\/a> and worst-case complexity<\/a> of O(N2<\/sup>).\u00a0<\/strong>This makes the algorithm less efficient when compared to algorithms such as quicksort<\/a> and merge sort<\/a>.\u00a0<\/p>\n Let’s assess how insertion sort performs by measuring the time it takes for it to sort an array.\u00a0For these tests, we are going to measure both the imperative<\/a> and recursive implementations<\/a> of the insertion sort algorithm.\u00a0\u00a0<\/p>\n First, let’s write a method to generate a set of random array elements:<\/p>\n The Next, we are going to define a method that generates a sequence of elements. This method simulates a scenario where we have a sorted array:<\/p>\n To make the tests as realistic as possible, we are going to use the inbuilt class We can create a simple method Next, we are going to create an object that holds different arrays that have random and sorted values:<\/p>\n Each object entry has three values: an integer array e.g.\u00a0 The array objects have different sizes (to simulate time complexity scenarios) and hold random numbers<\/a> that are added by the The Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:<\/p>\n The\u00a0recursive implementation<\/a> of the insertion sort algorithm is slower than its imperative implementation<\/a> in C# as it requires the allocation of a new stack frame every time From the benchmark, we can also see that the algorithm takes longer to sort reversed arrays, which simulates the algorithm’s worst-case complexity<\/a>. Let’s analyze the results obtained from sorting the largest array consisting of 20,000 elements. In this article, we have learned how insertion sort in C# works. It is simple to implement and use but it is not efficient.\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":" We have different sorting algorithms that we can use when we want to sort lists of elements. Insertion sort is one of the simplest algorithms that we can use to achieve our goal. In this article, we learn how insertion sort works, implement the algorithm in C#, and analyze its time and space complexity.\u00a0 Let’s […]<\/p>\n","protected":false},"author":6,"featured_media":62189,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[1010,12],"tags":[1140,1218,1219,592,1141],"class_list":["post-69254","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-csharp","tag-algorithm","tag-insertion-c","tag-insertion-sort","tag-sorting","tag-sorting-algorithm","et-has-post-format-content","et_post_format-et-post-format-standard"],"yoast_head":"\nint[] array = { 86, 13, 60, 46, 73, 52 };<\/code><\/p>\n13<\/span>, 86<\/span>, 60, 46, 73, 52<\/code><\/p>\n13<\/span>, 60<\/span>, 86<\/span>, 46, 73, 52<\/code><\/p>\n13<\/span>, 60<\/span>, 46<\/span>, 86<\/span>, 73, 52<\/code><\/p>\n13<\/span>, 46<\/span>, 60<\/span>, 86<\/span>, 73, 52<\/code><\/p>\n13<\/span>, 46<\/span>, 60<\/span>, 73<\/span>, 86<\/span>, 52<\/code><\/p>\n13<\/span>, 46<\/span>, 60<\/span>, 73<\/span>, 52, 86<\/span><\/code><\/p>\n13<\/span>, 46<\/span>, 60<\/span>, 52, 73<\/span>, 86<\/span><\/code><\/p>\n13<\/span>, 46<\/span>, 52,<\/span> 60<\/span>, 73<\/span>, 86<\/span><\/code><\/p>\n\n
<\/a>How to Implement Insertion Sort in C#?<\/h2>\n
<\/a>Imperative Implementation<\/h3>\n
SortArray()<\/code> as our entry point into the sorting algorithm. The method takes int[] array<\/code> and int length<\/code> as inputs:<\/p>\npublic int[] SortArray(int[] array, int length)\r\n{\r\n for (int i = 1; i < length; i++)\r\n {\r\n var key = array[i];\r\n var flag = 0;\r\n\r\n for (int j = i - 1; j >= 0 && flag != 1;)\r\n {\r\n if (key < array[j])\r\n {\r\n array[j + 1] = array[j];\r\n j--;\r\n array[j + 1] = key;\r\n }\r\n else flag = 1;\r\n }\r\n }\r\n\r\n return array;\r\n}<\/pre>\nSortArray()<\/code> uses two nested loops to sort the array elements. We can see that the iteration process starts from the second element\u00a0i = 1<\/code>.<\/p>\nkey = array[i]<\/code> is inserted into its correct position in the array. The inner loop checks if the current element is less than, which is the last element in the sorted segment of the array. If key < array[j]<\/code>\u00a0is true, we shift their positions, otherwise, we set the flag<\/code> variable to 1 to allow the outer loop to iterate:<\/p>\nfor (int j = i - 1; j >= 0 && flag != 1;)\r\n{\r\n if (key < array[j])\r\n {\r\n array[j + 1] = array[j];\r\n j--;\r\n array[j + 1] = key;\r\n }\r\n else flag = 1;\r\n}<\/pre>\nSortArray()<\/code> method sorts a given unsorted array accurately:<\/p>\nvar array = new int[] { 73, 57, 49, 99, 133, 20, 1 };\r\nvar expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };\r\nvar sortFunction = new InsertionSortMethods();\r\n\r\nvar sortedArray = sortFunction.SortArray(array, array.Length);\r\n\r\nAssert.IsNotNull(sortedArray);\r\nCollectionAssert.AreEqual(sortedArray, expected);<\/pre>\n<\/a>Recursive Implementation<\/h3>\n
SortArrayRecursive()<\/code> that takes array<\/code> and length<\/code> as inputs:<\/p>\npublic int[] SortArrayRecursive(int[] array, int length) \r\n{\r\n if (length <= 1)\r\n {\r\n return array;\r\n }\r\n\r\n SortArrayRecursive(array, length - 1);\r\n var key = array[length - 1];\r\n var k = length - 2;\r\n\r\n while (k >= 0 && array[k] > key)\r\n {\r\n array[k + 1] = array[k];\r\n k = k - 1;\r\n }\r\n\r\n array[k + 1] = key;\r\n\r\n return array;\r\n}<\/pre>\nif (length <= 1)\r\n{\r\n return array;\r\n}<\/pre>\nSortArrayRecursive()<\/code> calls itself while passing the array<\/code> and length -1<\/code> as its parameters.\u00a0<\/p>\narray[length - 1]<\/code>), we assign it to key<\/code> . k<\/code> holds the second last element of the array, which we are going to compare against key<\/code>.\u00a0<\/p>\nk<\/code> it with key<\/code> . We shift their positions if k<\/code> are greater than key<\/code>:\u00a0<\/p>\nwhile (k >= 0 && array[k] > key)\r\n{\r\n array[k + 1] = array[k];\r\n k = k - 1;\r\n}<\/pre>\nSortArrayRecursive()<\/code> method sorts a given unsorted array accurately:<\/p>\nvar array = new int[] { 73, 57, 49, 99, 133, 20, 1 };\r\nvar expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };\r\nvar sortFunction = new InsertionSortMethods();\r\n\r\nvar sortedArray = sortFunction.SortArrayRecursive(array, array.Length);\r\n\r\nAssert.IsNotNull(sortedArray);\r\nCollectionAssert.AreEqual(sortedArray, expected);<\/pre>\n<\/a>Space and Time Complexity of Insertion Sort Algorithm<\/h2>\n
<\/a>Best-Case Time Complexity<\/h3>\n
<\/a>Average-Case Time Complexity<\/h3>\n
<\/a>Worst-Case Time Complexity<\/h3>\n
<\/a>Advantages of Insertion Sort Algorithm<\/h2>\n
<\/a>Disadvantages of Insertion Sort Algorithm<\/h2>\n
<\/a>Performance Tests<\/h2>\n
public static int[] CreateRandomArray(int size)\r\n{\r\n var array = new int[size];\r\n var rand = new Random();\r\n\r\n for (int i = 0; i < size; i++)\r\n array[i] = rand.Next();\r\n\r\n return array;\r\n}<\/pre>\nCreateRandomArray()<\/code> the method takes an integer as its sole input. Using the inbuilt Random<\/code> class, we generate integer values that we’re going to put into the array.<\/p>\npublic static int[] CreateSortedArray(int size)\r\n{\r\n var array = new int[size];\r\n\r\n for (int i = 0; i < size; i++)\r\n array[i] = i;\r\n\r\n return array;\r\n}<\/pre>\nArray.Reverse()<\/code> to reverse the arrays generated from the CreateSortedArray()<\/code> method.\u00a0<\/p>\nCreateReversedArray()<\/code> that takes an int[] array<\/code> as its sole parameter and returns a reversed array:<\/p>\npublic static int[] CreateReversedArray(int[] array)\r\n{\r\n Array.Reverse(array);\r\n\r\n return array;\r\n}<\/pre>\npublic IEnumerable<object[]> SampleArrays()\r\n{\r\n yield return new object[] { CreateRandomArray(200), 200, \"Small Unsorted\" };\r\n yield return new object[] { CreateRandomArray(2000), 2000, \"Medium Unsorted\" };\r\n yield return new object[] { CreateRandomArray(20000), 20000, \"Large Unsorted\" };\r\n yield return new object[] { CreateSortedArray(200), 200, \"Small Sorted\" };\r\n yield return new object[] { CreateSortedArray(2000), 2000, \"Medium Sorted\" };\r\n yield return new object[] { CreateSortedArray(20000), 20000, \"Large Sorted\" };\r\n yield return new object[] { CreateReversedArray(CreateSortedArray(200)), 200, \"Small Reversed\" };\r\n yield return new object[] { CreateReversedArray(CreateSortedArray(2000)), 2000, \"Medium Reversed\" };\r\n yield return new object[] { CreateReversedArray(CreateSortedArray(20000)), 20000, \"Large Reversed\" };\r\n}<\/pre>\nCreateRandomArray(200)<\/code>, its length (200), and a string object storing the name of that array (“Small Unsorted”).\u00a0<\/p>\nCreateRandomArray()<\/code> method.<\/p>\nCreateSortedArray()<\/code> the method creates arrays that have values that are sorted. On the other hand, CreateReversedArray()<\/code>creates reverses a sorted array to simulate worst-case complexity<\/a> scenarios.\u00a0<\/p>\n| Method | array | length | arrayName | Mean | Error | StdDev |\r\n|------------------- |------------- |------- |---------------- |-------------:|------------:|-------------:|\r\n| SortArray | Int32[200] | 200 | Small Reversed | 403.4 ns | 7.89 ns | 9.39 ns |\r\n| SortArrayRecursive | Int32[200] | 200 | Small Reversed | 1,055.7 ns | 21.12 ns | 41.69 ns |\r\n| SortArray | Int32[200] | 200 | Small Sorted | 400.2 ns | 7.72 ns | 6.84 ns |\r\n| SortArrayRecursive | Int32[200] | 200 | Small Sorted | 1,022.0 ns | 18.79 ns | 15.69 ns |\r\n| SortArray | Int32[200] | 200 | Small Unsorted | 398.9 ns | 7.62 ns | 5.95 ns |\r\n| SortArrayRecursive | Int32[200] | 200 | Small Unsorted | 1,031.8 ns | 19.95 ns | 24.50 ns |\r\n| SortArray | Int32[2000] | 2000 | Medium Reversed | 3,849.0 ns | 76.73 ns | 88.36 ns |\r\n| SortArrayRecursive | Int32[2000] | 2000 | Medium Reversed | 12,186.8 ns | 240.80 ns | 395.64 ns |\r\n| SortArray | Int32[2000] | 2000 | Medium Sorted | 3,850.5 ns | 73.60 ns | 78.75 ns |\r\n| SortArrayRecursive | Int32[2000] | 2000 | Medium Sorted | 12,077.7 ns | 240.66 ns | 286.49 ns |\r\n| SortArray | Int32[2000] | 2000 | Medium Unsorted | 3,958.1 ns | 77.61 ns | 211.15 ns |\r\n| SortArrayRecursive | Int32[2000] | 2000 | Medium Unsorted | 13,002.4 ns | 577.56 ns | 1,666.39 ns |\r\n| SortArray | Int32[20000] | 20000 | Large Reversed | 59,549.5 ns | 4,488.07 ns | 13,020.71 ns |\r\n| SortArrayRecursive | Int32[20000] | 20000 | Large Reversed | 160,805.7 ns | 3,094.82 ns | 3,800.72 ns |\r\n| SortArray | Int32[20000] | 20000 | Large Sorted | 36,877.7 ns | 681.48 ns | 669.31 ns |\r\n| SortArrayRecursive | Int32[20000] | 20000 | Large Sorted | 156,821.2 ns | 2,280.12 ns | 1,780.17 ns |\r\n| SortArray | Int32[20000] | 20000 | Large Unsorted | 36,467.7 ns | 483.45 ns | 452.22 ns |\r\n| SortArrayRecursive | Int32[20000] | 20000 | Large Unsorted | 158,289.3 ns | 2,164.03 ns | 1,807.06 ns |<\/pre>\n
SortArrayRecursive()<\/code> is at least two times slower than the imperative implementation SortArray()<\/code> in all cases. For example, when sorting a small reversed array, SortArrayRecursive()<\/code> takes approximately 1,056 ns while SortArray()<\/code> takes about 404 ns.<\/p>\nSortArrayRecursive()<\/code> calls itself.\u00a0\u00a0<\/p>\nSortArray()<\/code> takes almost twice as long to sort a reversed array (59,549.5 ns) as compared to sorting a randomized array (36,467.7 ns).<\/p>\n<\/a>Conclusion<\/h2>\n