· · ·
Insertion Sort
Given an array A[1…n] of length n to be sorted. The algorithm sorts the list inplace. It picks an element i as key and places it in the correct position in the sorted A[1..(i-1)].
Time Complexity: \(O(n^2)\)
Space Complexity: \(O(n)\)
Pseudocode
InsertionSort(A):
for i = 1 to A.length-1
key = A[i]
j = i - 1
while j > 0 and a[j] > key:
A[j+1] = A[j]
j--
A[j+1] = key
Java Code
public class InsertionSort {
public int[] insertionSort(int[] arr) {
int length = arr.length;
int key, j, i;
for(j = 1; j < length; j++) {
key = arr[j];
i = j-1;
while(i >= 0 && arr[i] > key) {
arr[i+1] = arr[i];
i--;
}
arr[i+1] = key;
}
return arr;
}
public static void print_arr(int[] arr) {
for(int i: arr) {
System.out.printf("%d ", i);
}
}
public static void main(String[] args) {
InsertionSort i = new InsertionSort();
int[] arr = {9, 8, 7, 6, 5};
int[] sorted = i.insertionSort(arr);
InsertionSort.print_arr(sorted);
}
}
REFERENCES:
· · ·