{"id":409,"date":"2023-04-06T21:43:02","date_gmt":"2023-04-06T21:43:02","guid":{"rendered":"https:\/\/vmlogger.com\/algorithms\/?p=409"},"modified":"2023-04-06T21:45:37","modified_gmt":"2023-04-06T21:45:37","slug":"insertion-sort-an-explanation-and-implementation","status":"publish","type":"post","link":"https:\/\/vmlogger.com\/algorithms\/2023\/04\/06\/insertion-sort-an-explanation-and-implementation\/","title":{"rendered":"Insertion Sort : An Explanation and Implementation"},"content":{"rendered":"
Insertion Sort is a simple, yet powerful algorithm for sorting data. The algorithm works by taking one element at a time from an unsorted list and inserting it into a sorted list in the correct position. In this article, we will learn how the Insertion Sort algorithm works and its implementation in Python. Refer the below-animated visualization of insertion sort: \n
The Insertion Sort algorithm works as follows:<\/p>\n
\n
Take an unsorted list of n elements.<\/li>\n
Pick the first element and insert it into a sorted list.<\/li>\n
Take the next element and insert it into the sorted list in the correct position.<\/li>\n
Repeat step 3 until all elements have been inserted into the sorted list.<\/li>\n<\/ol>\n
\nThe key to the Insertion Sort algorithm is in step 3. To insert an element into a sorted list, we compare it with the elements already in the sorted list, starting from the rightmost element. If the element is smaller than the element to its left, we swap them. We continue this process until the element is in the correct position.\n<\/div>\n
Step-by-step Explanation of Insertion sort<\/h2>\n
Let’s take a closer look at how the algorithm works with an example:<\/p>\n
\nSuppose we have an unsorted list [5, 2, 4, 6, 1, 3]<\/code>. \nWe start by picking the first element, 5<\/code>, and inserting it into a sorted list [5]<\/code>. \nWe then take the second element, 2<\/code>, and compare it with 5<\/code>. Since 2<\/code> is smaller than 5<\/code>, we swap them, and the sorted list becomes [2, 5]<\/code>. \nWe then take the third element, 4<\/code>, and insert it into the sorted list. \nWe compare 4<\/code> with 5<\/code> and swap them, giving us [2, 4, 5]<\/code>. \nWe continue this process until we have a sorted list of all elements.\n<\/div>\n
How to implement insertion sort in Python<\/h2>\n
\r\ndef insertionSort(arrayToSort):\r\n \"\"\"\r\n Complexity:\r\n best : O(n)\r\n average : O(n^2)\r\n worst : O(n^2)\r\n parameters:\r\n arrayToSort: Array to be sorted\r\n\r\n returns:\r\n sorted array\r\n \"\"\"\r\n for i in range(1, len(arrayToSort)):\r\n j = i\r\n while j > 0 and arrayToSort[j] < arrayToSort[j - 1]:\r\n arrayToSort[j], arrayToSort[j - 1] = arrayToSort[j - 1], arrayToSort[j]\r\n j -= 1\r\n return arrayToSort\r\n\r\n\r\nif __name__ == \"__main__\":\r\n array = [2, 5, 1, 5, 8, 9, 0, 10]\r\n print(insertionSort(array))\r\n<\/pre>\n
Conclusion:<\/h2>\n
In summary, Insertion Sort is a simple and efficient algorithm for sorting data. It works by inserting each element into a sorted list in the correct position. While Insertion Sort is less efficient than Merge Sort for large datasets, it can be more efficient than Bubble Sort for small datasets. It is important to choose the appropriate sorting algorithm depending on the size of the dataset and the specific use case.<\/p>\n<\/span>","protected":false},"excerpt":{"rendered":"
Insertion Sort is a simple, yet powerful algorithm for sorting data. The algorithm works by taking one element at a time from an unsorted list and inserting it into a sorted list in the correct position. In this article, we will learn how the Insertion Sort algorithm works and its implementation in Python. Refer the […]<\/p>\n","protected":false},"author":45,"featured_media":421,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[3,10],"tags":[],"class_list":["post-409","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-easy","category-sorting"],"yoast_head":"\n
Insertion Sort : An Explanation and Implementation - Algorithms<\/title>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\t\n\t\n\t\n\n\n\n\n\n\t\n\t\n\t\n