Alg.6 Insertion Sort

From algoexpert.io

We apply Insertion Sort to sort the given arrays. For the Insertion Sort, we basically separate the original array into 2 parts, “ordered” one and “disordered” one. First, we iterate the array from the second element if the length of the original array is no less than 2. Tha idea is we pick a element from the “disordered” collection, find the expecting position in the “ordered” one, then insert the element into the “ordered” one.

Here are the code implementations, two ways are basically apply the same conception.

public static int[] insertionSort(int[] array) {
    // Write your code here.
        for (int i = 1; i < array.length; i++){
            int value = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > value) array[j + 1] = array[j];
                else break;
            }
            array[j + 1] = value;
        }
    return array;
  }

Time complexity: O(n^2); Space complexity: O(1)

public static int[] insertionSort(int[] array) {
    // Write your code here.
        for (int i = 1; i < array.length; i++) {
            while (i > 0) {
                if (array[i - 1] > array[i]) {
                    swap(array, i, i - 1);
                    i--;
                } else break;
            }
        }
    return array;
  }

Time complexity: O(n^2); Space complexity: O(1)

Donate