Skip to main content

Insertion Sort


Insertion sort is a simple and straightforward sorting algorithm that is based on the idea of dividing the input into two parts: the sorted and unsorted sublists. The algorithm starts by considering the first element of the input as the only element in the sorted sublist, and the rest of the elements are considered part of the unsorted sublist. The idea behind the insertion sort algorithm is to iteratively take the first element from the unsorted sublist and insert it into the correct position in the sorted sublist.

The algorithm works by comparing the current element with each element in the sorted sublist and shifting elements to the right to make space for the current element until a position is found where the current element is greater than or equal to the element to its left and less than or equal to the element to its right. This position is the correct place to insert the current element into the sorted sublist.

Insertion sort is an in-place sorting algorithm, meaning that it sorts the input in-place and does not require any additional memory to sort the input. This makes it a good choice for sorting small datasets, where the overhead of allocating additional memory for sorting becomes significant.

The time complexity of the insertion sort algorithm is O(n^2) in the worst case and O(n) in the best case (when the input is already sorted). This means that for a dataset of size n, the algorithm will take n^2 steps to sort the input in the worst case. The best case time complexity of O(n) means that for a dataset of size n, the algorithm will take n steps to sort the input in the best case.

One of the advantages of the insertion sort algorithm is that it is a stable sorting algorithm. This means that it maintains the relative order of equal elements in the input. For example, if the input contains two elements with the same value, the algorithm will preserve their order in the sorted sublist.

Another advantage of the insertion sort algorithm is that it is simple to understand and implement. The algorithm can be easily written in a few lines of code, and its behavior is straightforward, making it a good choice for educational purposes and for sorting small datasets.

Despite its simplicity, the insertion sort algorithm has several disadvantages that make it an inefficient choice for sorting large datasets. Firstly, its time complexity of O(n^2) in the worst case makes it inefficient for large datasets, where more efficient sorting algorithms such as QuickSort, MergeSort, and HeapSort can be used.

Secondly, the insertion sort algorithm is not well suited for sorting datasets with large amounts of data that are randomly ordered. In such cases, the algorithm would have to perform a large number of comparisons and shifts, making it an inefficient choice.

Finally, the insertion sort algorithm is not efficient for sorting datasets with a large number of elements that are nearly sorted. In such cases, the algorithm would still have to perform a large number of comparisons and shifts, making it an inefficient choice.

ALGORITHM:

The algorithm follows the following steps:

1. Take the first element of the unsorted sublist as the current element.
2. Compare the current element with each element in the sorted sublist.
3. Shift the elements to the right until a position is found where the current element is greater than or equal to the element to its left and less than or equal to the element to its right.
4. Insert the current element into the found position.
5. Repeat steps 1-4 for each element in the unsorted sublist.
6. Once all the elements have been processed, the sorted sublist will contain all the elements in sorted order.

PSEUDO CODE:

Here is the pseudo-code for the Insertion Sort algorithm:


The algorithm starts by looping through the input array from the second element (index 1) to the last element. For each iteration, the current element is stored in a variable called key. The variable j is initialized to i - 1 and is used to iterate through the sorted sublist, comparing the key to each element in the sorted sublist. If the key is smaller than the element at j, it is shifted to the right and j is decremented until either j becomes negative or key is greater than or equal to the element at j. Finally, the key is inserted into the position j + 1 in the sorted sublist. The algorithm repeats these steps for each element in the unsorted sublist, and the sorted sublist grows in size after each iteration until all elements are processed and the input array is sorted.

PYTHON CODE:

Here is the Python code for the Insertion Sort algorithm:


The function insertion_sort takes an array as input and sorts it using the Insertion Sort algorithm. The algorithm starts by looping through the input array from the second element (index 1) to the last element. For each iteration, the current element is stored in a variable called key. The variable j is initialized to i - 1 and is used to iterate through the sorted sublist, comparing the key to each element in the sorted sublist. If the key is smaller than the element at j, it is shifted to the right and j is decremented until either j becomes negative or key is greater than or equal to the element at j. Finally, the key is inserted into the position j + 1 in the sorted sublist. The algorithm repeats these steps for each element in the unsorted sublist, and the sorted sublist grows in size after each iteration until all elements are processed and the input array is sorted. The function returns the sorted array.

JAVA CODE:

Here is the Java code for the Insertion Sort algorithm:



The function insertionSort takes an array of integers as input and sorts it using the Insertion Sort algorithm. The algorithm starts by looping through the input array from the second element (index 1) to the last element. For each iteration, the current element is stored in a variable called key. The variable j is initialized to i - 1 and is used to iterate through the sorted sublist, comparing the key to each element in the sorted sublist. If the key is smaller than the element at j, it is shifted to the right and j is decremented until either j becomes negative or key is greater than or equal to the element at j. Finally, the key is inserted into the position j + 1 in the sorted sublist. The algorithm repeats these steps for each element in the unsorted sublist, and the sorted sublist grows in size after each iteration until all elements are processed and the input array is sorted. The function returns the sorted array.

C CODE:

Here is the C code for the Insertion Sort algorithm:



The function insertionSort takes an array of integers and its size as input and sorts it using the Insertion Sort algorithm. The algorithm starts by looping through the input array from the second element (index 1) to the last element. For each iteration, the current element is stored in a variable called key. The variable j is initialized to i - 1 and is used to iterate through the sorted sublist, comparing the key to each element in the sorted sublist. If the key is smaller than the element at j, it is shifted to the right and j is decremented until either j becomes negative or key is greater than or equal to the element at j. Finally, the key is inserted into the position j + 1 in the sorted sublist. The algorithm repeats these steps for each element in the unsorted sublist, and the sorted sublist grows in size after each iteration until all elements are processed and the input array is sorted. The sorted array is then printed to the console.

C++ CODE:

Here is the C++ code for the Insertion Sort algorithm:



The function insertionSort takes an array of integers and its size as input and sorts it using the Insertion Sort algorithm. The algorithm starts by looping through the input array from the second element (index 1) to the last element. For each iteration, the current element is stored in a variable called key. The variable j is initialized to i - 1 and is used to iterate through the sorted sublist, comparing the key to each element in the sorted sublist. If the key is smaller than the element at j, it is shifted to the right and j is decremented until either j becomes negative or key is greater than or equal to the element at j. Finally, the key is inserted into the position j + 1 in the sorted sublist. The algorithm repeats these steps for each element in the unsorted sublist, and the sorted sublist grows in size after each iteration until all elements are processed and the input array is sorted. The sorted array is then printed to the console.

JAVASCRIPT CODE:

Here is the JavaScript code for the Insertion Sort algorithm:



The function insertionSort takes an array of integers as input and sorts it using the Insertion Sort algorithm. The algorithm starts by looping through the input array from the second element (index 1) to the last element. For each iteration, the current element is stored in a variable called key. The variable j is initialized to i - 1 and is used to iterate through the sorted sublist, comparing the key to each element in the sorted sublist. If the key is smaller than the element at j, it is shifted to the right and j is decremented until either j becomes negative or key is greater than or equal to the element at j. Finally, the key is inserted into the position j + 1 in the sorted sublist. The algorithm repeats these steps for each element in the unsorted sublist, and the sorted sublist grows in size after each iteration until all elements are processed and the input array is sorted. The sorted array is then printed to the console.

Comments

Post a Comment

Popular posts from this blog

Bubble Sort

   Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array. The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted. Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array. The second pass would start with comparing 3 and 5,...
Post a Comment
Read more

Shell Sort

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an extension of the insertion sort algorithm and is classified as an in-place comparison sort. Shell sort aims to improve the performance of insertion sort by sorting elements that are far apart from each other first, thus reducing the number of comparisons needed to sort the entire array. The algorithm works by first dividing the array into smaller subarrays, each containing elements that are a certain gap apart. The gap is typically initialized to be the length of the array divided by 2, and is then halved in each iteration until it becomes 1. The subarrays are then sorted using insertion sort, which sorts elements within each subarray by comparing adjacent elements and swapping them if they are in the wrong order. The key idea behind Shell sort is that insertion sort performs poorly on arrays that are almost sorted, but works well on small arrays. By sorting the subarrays with larger gaps first, the algorithm...
Post a Comment
Read more

Comb Sort

Comb sort is a sorting algorithm that was first proposed by Włodzimierz Dobosiewicz in 1980. The algorithm is a variation of bubble sort, and it is designed to improve upon the performance of bubble sort by using a larger gap between elements during the comparison phase of the algorithm. The basic idea behind comb sort is to compare elements that are separated by a large gap, and gradually reduce the gap between elements until the gap is equal to 1. The gap between elements is known as the "comb" in comb sort, and it is initially set to be the size of the input array being sorted. The size of the comb is then reduced by a factor known as the shrink factor, which is typically set to 1.3. During each pass of the algorithm, elements that are separated by the current gap are compared and swapped if they are out of order. The gap between elements is then reduced by the shrink factor, and the process is repeated until the gap is equal to 1. Once the gap is equal to 1, the algorithm...
Post a Comment
Read more