Sort the following data by using insertion sort. 18, 7, 22, 3, 14, 2
Insertion Sort Algorithm in C
Start with the second element (index 1) as the key.
Compare the key with the elements before it.
If the key is smaller, shift the compared element right.
Insert the key where the shifting of elements stops.
Repeat steps 2-4 for all elements in the unsorted part of the list.
Insertion Sort Logic:
For each element, we compare it with the elements before it.
If the previous elements are larger, we shift them right.
We insert the current element (key) in the correct position.
Sorting Process:
Step-by-Step Execution
Initial Array: {18, 7, 22, 3, 14, 2}
Pass 1:
Key = 7, compare with 18 → Shift 18 → Insert 7
Array: {7, 18, 22, 3, 14, 2}
Pass 2:
Key = 22, no shifting needed → Array stays the same
Pass 3:
Key = 3, compare with 22, 18, 7 → Shift all → Insert 3
Array: {3, 7, 18, 22, 14, 2}
Pass 4:
Key = 14, compare with 22, 18 → Shift 22, 18 → Insert 14
Array: {3, 7, 14, 18, 22, 2}
Pass 5:
Key = 2, compare with all → Shift all → Insert 2
Array: {2, 3, 7, 14, 18, 22}
#include <stdio.h>
int main() {
int A[6] = {18, 7, 22, 3, 14, 2}; // Initialize the array
int i, j, key;
// Sorting the array using Insertion Sort logic
for (i = 1; i < 6; i++)
{
key = A[i]; // Store the current element as the key
for (j = i-1; A[j] > key; j--) // for (j = i - 1; j >= 0 && A[j] > key; j--)
{
A[j + 1] = A[j]; // Move element to the right
}
A[j + 1] = key; // Insert the key at the correct position
}
// Display the sorted array
printf("After Sorting: ");
for (i = 0; i < 6; i++) {
printf("%d ", A[i]);
}
printf("\n");
return 0;
}
Example of j in Action
When i = 1 (key = 7):
j starts at 0: Compare key (7) with A[0] (18).
Since 18 > 7, shift 18 to the right (A[1] = A[0]).
When i = 2 (key = 22):
j starts at 1: Compare key (22) with A[1] (18).
Since 22 is not less than 18, no shifting occurs; 22 remains in place.
When i = 3 (key = 3):
j starts at 2: Compare key (3) with A[2] (22).
Since 22 > 3, shift 22 to the right (A[3] = A[2]).
j becomes 1: Compare key (3) with A[1] (18).
Since 18 > 3, shift 18 to the right (A[2] = A[1]).
j becomes 0: Compare key (3) with A[0] (7).
Since 7 > 3, shift 7 to the right (A[1] = A[0]).
Insert key (3) at A[0].
When i = 4 (key = 14):
j starts at 3: Compare key (14) with A[3] (22).
Since 22 > 14, shift 22 to the right (A[4] = A[3]).
j becomes 2: Compare key (14) with A[2] (18).
Since 18 > 14, shift 18 to the right (A[3] = A[2]).
j becomes 1: Compare key (14) with A[1] (7).
Since 7 is not greater than 14, insert key (14) at A[2].
When i = 5 (key = 2):
j starts at 4: Compare key (2) with A[4] (22).
Since 22 > 2, shift 22 to the right (A[5] = A[4]).
j becomes 3: Compare key (2) with A[3] (18).
Since 18 > 2, shift 18 to the right (A[4] = A[3]).
j becomes 2: Compare key (2) with A[2] (14).
Since 14 > 2, shift 14 to the right (A[3] = A[2]).
j becomes 1: Compare key (2) with A[1] (7).
Since 7 > 2, shift 7 to the right (A[2] = A[1]).
j becomes 0: Compare key (2) with A[0] (3).
Since 3 > 2, shift 3 to the right (A[1] = A[0]).
Insert key (2) at A[0].
