Insertion Sort Program in C

Insertion Sort in C is an easy and green sorting set of rules that creates the final taken care of array one detail at a time. It is typically implemented while the person has a small statistics set.

What is Insertion Sort?

Insertion Sort is a sorting algorithm where the array is sorted by taking one element at a time. The principle behind insertion sort is to take one element, iterate through the sorted array & find its correct position in the sorted array.

• Small arrays or lists can be sorted using the straightforward and effective sorting method called insertion sort.
• The algorithm operates by repeatedly inserting elements from the array's unsorted portion into the sorted portion in the appropriate sorted and unsorted components of the array that should be separated.
• This is the core idea of insertion sort Array's first detail is initially determined in the looked-after component, while the subsequent factors are observed within the unsorted portion.
• It selects every element one by one and inserts it into the looked-after part of the array in which it belongs.
•  The method compares the detail with every element within the taken care of half of the array, starting with the final element, after which it advances every element up thru one role till it determines the proper role for the new element.
• Once the appropriate region is mounted, the new element is introduced to the array's looked-after segment.
• The insertion sort method's worst-case time complexity, where n is the array's element count, is O(n2).

Due to its efficiency for small arrays, insertion sort can be slow for more extensive arrays. Insertion sort differs from other sorting algorithms in a few ways. It is practical when memory is constrained because it is straightforward to implement and only needs O(1) additional memory.

The straightforward sorting method, called insertion sort in C, divides the given array into sorted and unsorted portions. Then, it selects the appropriate values from the unsorted portions and inserts them into the sorted portions in the proper positions.

HOW TO IMPLEMENT INSERTION SORT IN C:

An insertion sort is a quick and effective approach for sorting small arrays or lists. A sorted listing is created by setting each detail in the appropriate region inside an unsorted listing. The sorted listing expands this way, one access at a time until the entire list is sorted.

Example – 1:

#include <stdio.h>
void insert(int a[], int n) /* function to sort an aay with insertion sort */
{
 int i, j, temp;
 for (i = 1; i < n; i++) {
 temp = a[i];
 j = i - 1;
 while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead from their current position*/
 {
 a[j+1] = a[j];
 j = j-1;
 }
 a[j+1] = temp;
 }
}
void printArr(int a[], int n) /* function to print the array */
{
 int i;
 for (i = 0; i < n; i++)
 printf("%d ", a[i]);
}
int main()
{
Int a[] = 12, 31, 25, 8, 32, 17 ;
 int n = sizeof(a) / sizeof(a[0]);
 printf("Before sorting array elements are - \n");
 printArr(a, n);
 insert(a, n);
 printf("\nAfter sorting array elements are - \n");
 printArr(a, n);
 return 0;
}

OUTPUT:

Example – 2:

#include <math.h>
#include <stdio.h>
/* Function to sort an array using insertion sort*/
void insertion sort(int arr[], int n)
{
 int i, key, j;
For (i = 1; i &lt; 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 sizes n
void printArray(int arr[], int n)
{
 int I;
 for (i = 0; i < n; i++)
 printf("%d ", arr[i]);
 printf("\n");
}
/* Driver program to test insertion sort */
int main()
{
 insertionSort(arr, n);
 printArray(arr, n);
 return 0;
}

OUTPUT:

To use this characteristic, you could create an array of integers and skip it to the characters like this:

1. This code produces an array of numbers and sends it, along with its length n, to the insertion sort function.
2. After sorting the array, the program utilizes a for loop to print the sorted array.
3. The Insertion Sort technique is effective for small arrays but slows for large arrays since its worst-case time complexity is O(n2).
4.  Nevertheless, it has some benefits over other sorting algorithms, including simplicity and ease of use.
5. For instance, an array's lower portion is kept and sorted.
6.  An element that needs to be "inserted" into this sorted sub-list must first determine where it belongs before doing so. Thus, insertion sort was born.

CONCLUSION:

In conclusion, the Insertion Sort algorithm can effectively sort tiny arrays or lists and is simple to implement in C. The method operates by adding each element to a sorted list one at a time and putting them into the appropriate positions. You may quickly sort your data with this technique without worrying about complicated sorting algorithms.