Scribd
Upload
7 views2 pages

Insertion Sort Example

Insertion Sort is a simple sorting algorithm that arranges elements by inserting them into their correct position one at a time. The document provides a step-by-step example of sorting the array [5, 3, 8, 4, 2], resulting in the sorted array [2, 3, 4, 5, 8]. It also includes a C program implementation of the Insertion Sort algorithm.

Uploaded by

bhardwajkrishiv128
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views2 pages

Insertion Sort Example

Insertion Sort is a simple sorting algorithm that arranges elements by inserting them into their correct position one at a time. The document provides a step-by-step example of sorting the array [5, 3, 8, 4, 2], resulting in the sorted array [2, 3, 4, 5, 8]. It also includes a C program implementation of the Insertion Sort algorithm.

Uploaded by

bhardwajkrishiv128
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Insertion Sort with Example

What is Insertion Sort?


Insertion Sort is a simple sorting algorithm that works the way we sort playing cards in our
hands. It builds the sorted array one element at a time by repeatedly taking the next
element and inserting it into its correct position.

Step-by-Step Example
Consider the following array to be sorted in ascending order:
Array: [5, 3, 8, 4, 2]

Step 1: Take 3 and insert into sorted part → [3, 5, 8, 4, 2]


Step 2: Take 8 → already in order → [3, 5, 8, 4, 2]
Step 3: Take 4 and insert into correct place → [3, 4, 5, 8, 2]
Step 4: Take 2 and insert into correct place → [2, 3, 4, 5, 8]

Now the array is sorted: [2, 3, 4, 5, 8]

Algorithm (Insertion Sort)


1. Start with the second element (first element is considered sorted).
2. Compare the current element with the elements in the sorted part.
3. Shift all elements greater than the current element to one position ahead.
4. Insert the current element into its correct position.
5. Repeat until the array is sorted.

C Program for Insertion Sort


#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}

You might also like