Sort an array using insertion sort using the C programming language

Sort an array using insertion sort using the C programming language

Code:

#include <stdio.h>

void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int 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--;
}
arr[j + 1] = key;
}
}

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {12, 11, 13, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");
printArray(arr, size);

insertionSort(arr, size);

printf("Sorted array: ");
printArray(arr, size);

return 0;
}

Copy and paste this code into a C compiler, and it should sort the array using the insertion sort algorithm. The insertionSort function takes an array and its size as arguments and sorts the array in ascending order. The printArray function is used to print the contents of an array. The main function demonstrates the usage of the sorting function on a sample array.

Explanation:

#include <stdio.h>

This line includes the standard input-output library which provides functions like printf and scanf for input and output operations.

void insertionSort(int arr[], int size) {

This line starts the definition of the insertionSort function. It takes two arguments: an integer array arr and an integer size representing the size of the array.

for (int i = 1; i < size; i++) {

This line starts a for loop that iterates over each element of the array, starting from index 1 (because the element at index 0 is considered already sorted).

int key = arr[i];
int j = i - 1;

Here, we declare two variables: key to store the current element being considered for insertion, and j to keep track of the index before the current element.

while (j >= 0 && arr[j] > key) {

This line starts a while loop that continues as long as j is greater than or equal to 0 and the element at index j is greater than the key. This loop is used to find the correct position for the key in the sorted part of the array.

arr[j + 1] = arr[j];
j--;

Within the while loop, these lines shift elements that are greater than the key to the right by one position. This makes space for the key to be inserted in the correct position.

arr[j + 1] = key;

Once the correct position is found, this line assigns the value of key to the newly opened position, effectively inserting it into the correct place in the sorted part of the array.

}
}

This closes the for loop and completes the insertionSort function.

void printArray(int arr[], int size) {

This line starts the definition of the printArray function, which takes an integer array arr and an integer size as arguments.

for (int i = 0; i < size; i++) {

This line starts a for loop that iterates over each element of the array.

printf("%d ", arr[i]);

Within the loop, this line uses the printf function to print each element of the array followed by a space.

}
printf("\n");
}

This completes the printArray function. After the loop, a newline character is printed to move to the next line after printing the array.

int main() {

This is the beginning of the main function, the entry point of the program.

int arr[] = {12, 11, 13, 5, 6};

Here, we initialize an integer array arr with some sample values.

int size = sizeof(arr) / sizeof(arr[0]);

This line calculates the size of the array by dividing the total size of the array by the size of a single element.

printf("Original array: ");
printArray(arr, size);

These lines print the original array using the printArray function.

insertionSort(arr, size);

This line calls the insertionSort function to sort the array in place.

printf("Sorted array: ");
printArray(arr, size);

Finally, these lines print the sorted array using the printArray function.