KEMBAR78
I Sort | PDF
Scribd
Upload
7 views3 pages

I Sort

Insertion Sort is a straightforward sorting algorithm that arranges an array by building a sorted section one element at a time. The process involves comparing each element with those before it, shifting larger elements to the right, and inserting the current element into its correct position. The algorithm's time complexity is not specified in the document, but it typically operates in O(n^2) time in the average and worst cases.

Uploaded by

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

I Sort

Insertion Sort is a straightforward sorting algorithm that arranges an array by building a sorted section one element at a time. The process involves comparing each element with those before it, shifting larger elements to the right, and inserting the current element into its correct position. The algorithm's time complexity is not specified in the document, but it typically operates in O(n^2) time in the average and worst cases.

Uploaded by

urvashipadhiyar1947
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

https://youtu.be/mTNC0ERo-ZI?

si=6OU9RwZpb3V3RDQm&t=7
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item
at a time. It is much like sorting playing cards in your hands.

Algorithm:

1.​ Start with the second element (index 1) of the array.


2.​ Compare this element with the elements before it.
3.​ Shift all elements greater than this element one position to the right.
4.​ Insert the current element into its correct position.
5.​ Repeat for all elements in the array.

Pseudocode:

insertionSort(array)
for i from 1 to length(array) - 1
key = array[i]
j=i-1
while j >= 0 and array[j] > key
array[j + 1] = array[j]
j=j-1
array[j + 1] = key
●​ Outer Loop (for i from 1 to length(array) - 1):
○​ This loop goes through each element in the array starting from the second
one.
●​ Key Assignment (key = array[i]):
○​ The current element is stored in key, which will be compared to previous
elements.
●​ Inner Loop (while j >= 0 and array[j] > key):
○​ This loop checks all previous elements in the sorted section. It continues
as long as the index j is valid and the current value is greater than key.
○​ Shifting Elements: If array[j] is greater than key, then array[j] shifts
one position to the right (array[j + 1] = array[j]).
○​ Update Index: Decrease j to check the next element to the left.
●​ Insertion (array[j + 1] = key):
○​ Once the right spot is found (when the loop stops), insert the key in that
position.

Example:

For an array [5, 2, 9, 1], the process would look like this:

●​ Start with 5 (the first element is considered sorted).


●​ Compare and insert 2: [2, 5, 9, 1]
●​ Compare and insert 9: [2, 5, 9, 1] (no changes)
●​ Compare and insert 1: [1, 2, 5, 9]

By the end, the array is sorted in ascending order.

Insertion sort Time complexity

You might also like