0
Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
Insertion Sort in C
How Insertion Sort works in C
In this technique, we pick an Element and then insert it at the appropriate position in ascending and descending order.
The inspiration has been taken from playing cards
| Time Complexity | O(n2) |
| Best Case | Ω(n) |
| Worst Case | O(n2) |
| Aux. Space Complexity | O(1) |
| Best case when | Array is already sorted |
| Worst case when | Array is reverse sorted |
Insertion Sort in C
Insertion sort is just like how to sort playing cards in your hands. You pick one card and try to place that card in its correct position.
The array is kind of split into a sorted part and an unsorted part. A value from the unsorted part is picked and placed into its correct position in the sorted part.
Below are examples on how you can do the same.
Execution of Insertion Sort in C
Approach of Insertion Sort
- Iterate over the whole array, picking each item in the array once iteratively
- Call this picked item key
- If this key item is smaller than its predecessor, compare it to the item before
- To make space for this swapped item move items greater than key one position right
- Keep doing this until you find a smaller element than key element.
Code of Insertion Sort
Normal
Using Driver function
Normal
Run
#include<stdio.h>
// Function to print array
void display(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Main function to run the program
int main()
{
int array[] = {8, 6, 4, 20, 24, 2, 10, 12};
int size = sizeof(array)/sizeof(array[0]);
printf("Before Insertion sort: \n");
display(array, size);
int i, key, j;
for (i = 1; i < size; i++)
{
key = array[i];
j = i - 1;
/* Here the elements in b/w array[0 to i-1]
which are greater than key are moved ahead
by 1 position each*/
while (j >= 0 && array[j] > key)
{
array[j + 1] = array[j];
j = j - 1;
}
// placing element at its correct position
array[j + 1] = key;
}
printf("After Insertion sort: \n");
display(array, size);
return 0;
}
// Time Complexity : O(n^2)
// Auxiliary Space : O(1)
Output:
Before Insertion sort: 8 6 4 20 24 2 10 12 After Insertion sort: 2 4 6 8 10 12 20 24
Using Driver function
Run
#include<stdio.h>
// Here we are implementing Insertion sort
void insertionSort(int array[], int size)
{
int i, key, j;
for (i = 1; i < size; i++)
{
key = array[i];
j = i - 1;
/* Here the elements in b/w array[0 to i-1]
which are greater than key are moved ahead
by 1 position each*/
while (j >= 0 && array[j] > key)
{
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
/* Function to print array */
void display(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Main function to run the program
int main()
{
int array[] = {5, 3, 1, 9, 8, 2, 4, 7};
int size = sizeof(array)/sizeof(array[0]);
printf("Before Insertion sort: \n");
display(array, size);
insertionSort(array, size);
printf("After Insertion sort: \n");
display(array, size);
return 0;
}
// Time Complexity : O(n^2)
// Auxiliary Space : O(1)
Output:
Before Insertion sort: 5 3 1 9 8 2 4 7 After Insertion sort: 1 2 3 4 5 7 8 9
Some facts about Insertion sort
- Time Complexity: O(n2)
- Auxiliary Space: O(1)
- Best Case: Ω(n), when the array is already sorted
- Worst Case: Θ(n^2), when the array is reverse sorted.
- Algorithmic Paradigm: Incremental Approach
- Sorting In Place: Yes
- Stable: Yes
Advantages and Disadvantages of Insertion Sort
Advantages
- It is simple, small and easy to write.
- It doesn’t use a lot of overhead.
- It uses in place sorting, thus O(1) space requirements
- If data is almost sorted, then it can be very fast approaching O(n) and faster than Merge sort(for sorted data, and small N, else merge sort is faster)
- Efficient for (quite) small data sets.
Disadvantages
- Poor average time complexity of O(n2)
- If there are a large number of elements then it is inefficient
- Many items needs to be shifted to one insertion
Properties
- You will encounter the best case if the data is already or nearly sorted
- It will give worst-case results if the array is sorted in the opposite order as required
Time Complexity
For Linear Search
Best
Ω(n)
Average
O(n2)
Worst
Θ(n2)
Space Complexity
O(1)
Time Complexity
For Linear Search
Best
O(n)
Average
O(n2)
Worst
Θ(n2)
Space Complexity
O(1)
Question 1. How many passes does an insertion sort algorithm consist of? –
- N-1
- N-2
- N
- N2
(Flipkart – HackerEarth Test)
Explanation: An insertion algorithm consists of N-1 passes when an array of N elements is given.
Question 2. For the following question, how will the array elements look like after second pass?
35, 7, 64, 57, 28, 14
- 8, 21, 32, 34, 51, 64
- 8, 32, 34, 51, 64, 21
- 8, 34, 51, 64, 32, 21
- 8, 34, 64, 51, 32, 21
(TCS NQT)
Original Array :
35, 7, 64, 57, 28, 14
After Pass 1 : 7, 35, 64, 57, 28, 14
After Pass 2 : 7, 35, 64, 57, 28, 14 (no change)
After Pass 3 : 7, 35, 57, 64, 28, 21 (no swapping)
After Pass 4 : 7, 28, 35, 57, 64, 14 (no swapping)
Sorting
Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.
Login/Signup to comment