Insertion sort pick one element and check with its left element if left is bigger then current then swap it. complexity is O(n^2)
public class InsertionSort {
public static void main(String[] args) {
int[] arr = { 2, 4, 23, 54, 67, 23, 66, 35, 28, 9, 65, 876, 32,1,0,2,4,5 };
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(insertionSort((arr))));
}
private static int[] insertionSort(int[] arr) {
for(int i=1;i<arr.length;i++) {
int key = arr[i];
int j = i-1;
while(j >=0 && key<arr[j]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
j--;
}
}
return arr;
}
static int insertionSortTemp(int[] arr) {
int n = arr.length;
int counter = 0;
if(arr.length ==0)return 0;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
arr[j + 1] = key;
counter++;
}
}
return counter;
}
}
public class InsertionSort {
public static void main(String[] args) {
int[] arr = { 2, 4, 23, 54, 67, 23, 66, 35, 28, 9, 65, 876, 32,1,0,2,4,5 };
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(insertionSort((arr))));
}
private static int[] insertionSort(int[] arr) {
for(int i=1;i<arr.length;i++) {
int key = arr[i];
int j = i-1;
while(j >=0 && key<arr[j]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
j--;
}
}
return arr;
}
static int insertionSortTemp(int[] arr) {
int n = arr.length;
int counter = 0;
if(arr.length ==0)return 0;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
arr[j + 1] = key;
counter++;
}
}
return counter;
}
}