Insertion Sort in java

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;
      }
}




Post a Comment

Previous Post Next Post