Insertion Sort

Insertion sort functions as a sorting algorithm that relies on comparisons to arrange the eventual sorted array incrementally. The method involves segmenting the input array into two distinct sections: a sorted segment and an unsorted segment. At the beginning, the sorted section comprises solely the initial element, while the remaining array is categorized as unsorted.

The process involves moving through the unsorted segment, examining each element individually, and juxtaposing it with the elements in the ordered portion. It determines the accurate location for the current element within the ordered segment by displacing elements larger than it to the right. This adjustment generates room for the current element's insertion.

To execute the insertion, the algorithm initiates from the furthest right element within the arranged section and evaluates it against the present element. In cases where the sorted region's element is larger, it gets moved one place to the right. This sequence persists until determining the correct placement for the current element.

Once the appropriate location is identified, the algorithm incorporates the present element into the arranged section. This insertion process is iterated for each element within the unordered section, progressively enlarging the sorted portion until the complete array is organized.

Insertion sort functions as an in-place algorithm, signifying that it operates without the need for extra memory to execute the sorting process. This sorting technique is recognized for its stability, ensuring that the arrangement maintains the original order of elements that possess equivalent values.

The worst-case time complexity of insertion sort amounts to O(n^2), where n represents the quantity of elements within the provided array. Despite this, insertion sort may exhibit improved efficiency for smaller arrays or ones that are partially sorted. Should the input array already be sorted, the time complexity diminishes to O(n), showcasing its optimal performance in this best-case scenario. On average, the time complexity maintains at O(n^2), positioning insertion sort as less efficient when juxtaposed with advanced sorting techniques such as quicksort or mergesort.

Although it may not be the fastest option for sorting large arrays, insertion sort offers several benefits. Its simplicity and ease of implementation make it an ideal solution for handling smaller datasets or scenarios where straightforwardness is prioritized over speed. Moreover, it excels in sorting partially ordered or almost sorted arrays, leading to reduced comparisons and swaps when compared to alternative algorithms.

In summary, the insertion sort algorithm is a straightforward and easy-to-understand method of sorting data. It works by inserting elements into their proper places within a partially sorted array. Although it may not be the optimal solution for sorting large amounts of data quickly, it possesses its own advantages and can be valuable in specific situations.

History

The insertion sort procedure has a rich background and can be linked back to the early stages of computer science development. It was initially referenced by the computer expert and mathematician John von Neumann in 1945, even though the procedure was probably familiar prior to that era.

The fundamental idea behind insertion sort can be observed in card games such as poker or rummy. Participants frequently organize their cards by iteratively placing a new card into its appropriate place within the previously arranged hand. This manual arrangement approach served as the basis for creating the insertion sort algorithm.

The algorithm became well-known as computers emerged, requiring effective sorting techniques. During the initial stages of computing, there were constraints on memory capacity, making intricate sorting methods impractical. Due to its straightforward nature and proficiency in sorting small arrays, Insertion sort emerged as a favored option.

One of the earliest mentions of the insertion sort algorithm in the realm of computer programming can be traced back to Maurice Wilkes' book "The Preparation of Programs for an Electronic Digital Computer" in 1951. In this publication, Wilkes explained the algorithm as a method for arranging a series of numbers within a computer software.

Throughout time, insertion sort has undergone thorough examination and research. The time complexity and operational behavior of this sorting method have been comprehensively grasped. Scholars have contrasted insertion sort against alternative sorting algorithms and pinpointed its advantages and limitations.

While insertion sort might not offer the optimal efficiency for handling extensive datasets, it has proven to be valuable in different contexts. This sorting algorithm shines when working with smaller arrays or arrays that are already somewhat sorted. Its straightforward nature and efficient performance in such situations make it a favorable option.

Despite the emergence of more sophisticated sorting algorithms, insertion sort remains a significant sorting technique that is commonly taught and explored. Its simple implementation and easy-to-understand approach make it a valuable resource for comprehending sorting algorithms and grasping the core concepts of computer science.

Algorithm for Insertion Sort

• ✅ Start by defining the insertionSort function that takes an array arr and its size n as input.
• ✅ Declare three variables: i, key, and j.
• ✅ Iterate over the array starting from index 1 to n-1.
• ✅ Assign the value of arr[i] to the variable key.
• ✅ Assign the value of i-1 to j.
• ✅ While j is greater than or equal to 0 and the value at arr[j] is greater than key, perform the following steps:
• ✅ Assign the value of arr[j] to arr[j+1].
• ✅ Decrement the value of j by 1.
• ✅ Assign the value of key to arr[j+1].
• ✅ Repeat steps 3-5 until the entire array is sorted.
• ✅ Define the printArray function that takes an array arr and its size n as input.
• ✅ Iterate over the array from index 0 to n-1.
• ✅ Print the value of arr[i].
• ✅ Print a new line to separate the output.
• ✅ The sorting algorithm is complete.
• ✅ To use the insertionSort function, you can call it from the main function and pass the array to be sorted along with its size. Similarly, you can use the printArray function to display the sorted array.

Below is the program for insertion sort algorithm in C++:

// C++ program for insertion sort
#include <bits/stdc++.h>
using namespace std;
// Function to sort an array using
// insertion sort
void insertionSort(int arr[], int n)
{
	int i, key, j;
	for (i = 1; i < n; i++) {
		key = arr[i];
		j = i - 1;
		// Move elements of arr[0..i-1],
		// that are greater than key,
		// to one position ahead of their
		// current position
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j = j - 1;
		}
		arr[j + 1] = key;
	}
}
// A utility function to print an array
// of size n
void printArray(int arr[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
}
// Driver code
int main()
{
	int arr[] = { 12, 11, 13, 5, 6 };
	int N = sizeof(arr) / sizeof(arr[0]);
 
	insertionSort(arr, N);
	printArray(arr, N);
 
	return 0;
}

Output:

5 6 11 12 13
............
Process executed in 1.11 seconds
Press any key to continue.

Explanation:

Here's a step-by-step explanation of the given code:

• ✅ The code begins by including the necessary header files: <bits/stdc++.h> which includes most standard library headers and using namespace std; which allows the usage of standard library functions and objects without explicitly specifying the namespace.
• ✅ The insertionSort function is defined, which takes an array arr and its size n as parameters. This function implements the insertion sort algorithm to sort the array in ascending order.
• ✅ Inside the insertionSort function, a loop iterates from the second element (i = 1) to the last element of the array. Each iteration represents selecting an element to be inserted into the sorted subarray.
• ✅ The selected element is stored in the variable key. The variable j is set to the index of the element just before the selected element.
• ✅ A while loop checks if the element at index j is greater than the key and if j is within the valid range (greater than or equal to 0). This loop shifts the elements greater than the key one position to the right.
• ✅ After finding the correct position for the key element, it is inserted at j + 1 index in the array.
• ✅ The printArray function is defined to print the elements of the array arr of size n in a space-separated format.
• ✅ The main function is the entry point of the program. It initializes an array arr with values {12, 11, 13, 5, 6}.
• ✅ The variable N is assigned the size of the array arr by dividing the total size of the array by the size of a single element.
• ✅ The insertionSort function is called with arr and N as arguments to sort the array.
• ✅ The printArray function is called to display the sorted array.
• ✅ Finally, the main function returns 0, indicating successful execution of the program.
• ✅ The output is displayed as "5 6 11 12 13", which represents the sorted array.
• ✅ Overall, the code demonstrates the implementation of the insertion sort algorithm and sorts the given array in ascending order.

Time Complexity Analysis:

The time complexity of the Insertion Sort algorithm demonstrated in this codebase is O(n2) for both the worst and average scenarios, while in the best case, it is O(n).

The primary loop executes for O(n) iterations (where O(n) represents the array size), and during each iteration, the nested while loop has the potential to run a maximum of i times, with i representing the current index within the outer loop. In the scenario of the array being in reverse order, the inner loop will run its maximum iterations, leading to a time complexity of O(n^2) in the worst-case scenario. Conversely, if the array is already sorted, the inner loop will not run at all, resulting in a time complexity of O(n) in the best-case scenario.

Space Complexity Analysis:

The code's space complexity is O(1) because it conducts sorting in situ, avoiding the use of extra data structures that scale with the input size. The limited extra space is allocated for variables such as i, key, and j, which maintain a constant size irrespective of the array's input size.

In essence, the time complexity for this algorithm is O(n2) in both the worst-case scenario and the average case, with the best case being O(n). On the other hand, the space complexity remains constant at O(1) since the algorithm only requires a fixed amount of additional space.

Advantages of Insertion Sort

• ✅ Simplicity: Insertion sort is straightforward to understand and implement. It uses a simple comparison and swapping mechanism to sort the elements.
• ✅ Efficient for Small Inputs: Insertion sort performs well when the input size is small or the array is already partially sorted. It has relatively low overhead compared to more complex sorting algorithms.
• ✅ Online Sorting: Insertion sort is an online sorting algorithm, meaning it can efficiently handle data as it comes in one element at a time. This property makes it useful in scenarios where data is continuously being added or sorted dynamically.
• ✅ Space Efficiency: Insertion sort operates in-place, meaning it doesn't require additional memory to perform the sorting. It sorts the elements within the existing array itself.

Disadvantages of Insertion Sort:

• ✅ Quadratic Time Complexity: Insertion sort has an average and worst-case time complexity of O (n^2), making it inefficient for large input sizes. As the number of elements increases, the number of comparisons and shifts required grows exponentially.
• ✅ Lack of Adaptiveness: Insertion sort does not adapt well to already sorted or nearly sorted arrays. It still performs a full set of comparisons and shifts, even if the array is partially sorted.
• ✅ Not Suitable for Large Data Sets: Due to its quadratic time complexity, insertion sort becomes impractical for sorting large data sets. Other sorting algorithms such as merge sort or quicksort are more efficient in such scenarios.
• ✅ Performance Dependency on Input Order: The efficiency of insertion sort heavily depends on the initial order of the elements. If the array is reverse sorted, insertion sort will require the maximum number of comparisons and shifts, further increasing its time complexity.

To recap, although insertion sort is known for its simplicity, efficient use of space, and effectiveness with small or somewhat sorted arrays, its time complexity of O(n^2) and non-adaptive nature may not be ideal for extensive datasets or arrays that are already sorted. It's crucial to evaluate the input data's traits and the expected performance standards before selecting a sorting algorithm.

Applications of Insertion Sort

Insertion sort is a simple yet efficient sorting algorithm that can be applied to various scenarios. Here are some common applications of insertion sort:

• ✅ Small Data Sets: Insertion sort performs well on small data sets or arrays that are already partially sorted or nearly sorted. It has a relatively low overhead and performs efficiently for such cases.
• ✅ Online Sorting: Insertion sort is often used for sorting data in real-time or as it becomes available. It allows for incremental sorting, where new elements can be efficiently inserted into a sorted list.
• ✅ Partial Sorting: In some scenarios, only a portion of the data needs to be sorted. Insertion sort is effective in such cases as it can sort a small part of the data while leaving the remaining elements untouched.
• ✅ Auxiliary Sorting Algorithm: Insertion sort is frequently used as an auxiliary algorithm within other sorting algorithms. For example, in algorithms like QuickSort or Timsort, insertion sort is used for sorting small subarrays or as a fallback when the array size becomes small.
• ✅ Educational Purposes: Due to its simplicity and ease of understanding, insertion sort is commonly taught in computer science and programming courses. It serves as a fundamental example of a sorting algorithm and helps students grasp the basic concepts of sorting.
• ✅ Optimized for Linked Lists: Insertion sort is well-suited for sorting linked lists because it requires only constant extra space. It efficiently rearranges the links between the nodes, making it a practical choice for sorting linked data structures.

In general, insertion sort might not be the most optimal sorting algorithm for extensive or extremely disordered datasets. Nonetheless, its straightforward nature, appropriateness for particular situations, and educational significance render it a valuable algorithm across different use cases.