Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Insertion sort is more suitable for small data sets or nearly sorted data sets because of its simplicity and efficiency in those cases.
Consider an array with the following elements:
[12, 11, 13, 5, 6]
To sort this array using insertion sort, follow these steps:
Let's apply these steps to the example array:
Below is the pseudo code for the insertion sort algorithm:
function insertionSort(array)
for i = 1 to length(array) - 1 do
key = array[i]
j = i - 1
while j >= 0 and array[j] > key do
array[j + 1] = array[j]
j = j - 1
end while
array[j + 1] = key
end for
end function
Explanation:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Example usage:
array = [12, 11, 13, 5, 6]
print("Original array:", array)
sorted_array = insertion_sort(array)
print("Sorted array:", sorted_array) # Output: [5, 6, 11, 12, 13]
This Python program defines a function to perform insertion sort on an array. The function iterates through the array, compares the current element with the sorted elements, shifts the larger elements to the right, and inserts the current element at the correct position.