Java Community | Help. Code. Learn.•2y ago

Week 8 — How would you implement the insert sort sorting algorithm in Java?

Question of the Week #8

How would you implement the insert sort sorting algorithm in Java?

7 Replies

public static void insertSort(int[] arr) { int x = arr.length; for (int i = 1; i < x; ++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; } }

Submission from Xionate#6442

Eric McIntyre•2y ago

public static void insertSort(int[] array) { int n = array.length; for (int i = 1; i < n; i++) { int key = array[i]; int j = i - 1; while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j = j - 1; } array[j + 1] = key; } } In this implementation, the input array is sorted in-place, meaning that the original array is modified and reordered. The insert sort algorithm works by iterating over the array and inserting each element into its correct position relative to the elements that have already been sorted. Another Example for better understanding

Eric McIntyre•2y ago

// Insertion sort in Java import java.util.Arrays; class InsertionSort { void insertionSort(int array[]) { int size = array.length; for (int step = 1; step < size; step++) { int key = array[step]; int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change key<array[j] to key>array[j]. while (j >= 0 && key < array[j]) { array[j + 1] = array[j]; --j; } // Place key at after the element just smaller than it. array[j + 1] = key; } } // Driver code public static void main(String args[]) { int[] data = { 9, 5, 1, 4, 3 }; InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); } }

Submission from Hassam#3933

Eric McIntyre•2y ago

There's multiple different ways to implement an insertion sort in java. First we will do a simple loop-based sort on an array. For the purpose of demonstration we will use an int[] though this will work for any Comparable

void sort (int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int val = arr[i];
        int j;
        for (j = i - 1; j >= 0 && arr[j] > val; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = val;
    }
}

void sort (int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int val = arr[i];
        int j;
        for (j = i - 1; j >= 0 && arr[j] > val; j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = val;
    }
}

Eric McIntyre•2y ago

Here we shift each number to the left until we find the right spot for it where we "insert" it

⭐ Submission from jade#9418

Eric McIntyre•2y ago

In Java, an int[] can be sorted using InsertionSort like the following

void insertionSort(int[] arr){
    for(int i=1;i<arr.length;i++){//next element to shift
        for(int j=i;j>0&&arr[j-1]>arr[j];j--){//as long as there is a bigger element to the left of it
            int tmp=arr[j-1];//swap with previous element
            arr[j-1]=arr[j];
            arr[j]=tmp;
        }
    }
}

void insertionSort(int[] arr){
    for(int i=1;i<arr.length;i++){//next element to shift
        for(int j=i;j>0&&arr[j-1]>arr[j];j--){//as long as there is a bigger element to the left of it
            int tmp=arr[j-1];//swap with previous element
            arr[j-1]=arr[j];
            arr[j]=tmp;
        }
    }
}

InsertionSort works by iterating from the second element (the first one alone is always sorted) up to the end of the array and shifting that element to the left until it reaches a position where it is bigger than the previous element. This makes sure that all elements up to the currently shifted element are sorted before moving to the next element that is then shifted into its position in the already sorted subarray. For Lists of custom objects (using a Comparator), this can easily be adopted:

<T> void insertionSort(List<T> list, Comparator<T> comparator){
    for(int i=1;i<list.size();i++){
        for(int j=i;j>0&&comparator.compare(list.get(j-1),list.get(j))>0;j--){
            T tmp=list.get(j-1);
            list.set(j-1,list.get(j));
            list.set(j,tmp);
        }
    }
}

<T> void insertionSort(List<T> list, Comparator<T> comparator){
    for(int i=1;i<list.size();i++){
        for(int j=i;j>0&&comparator.compare(list.get(j-1),list.get(j))>0;j--){
            T tmp=list.get(j-1);
            list.set(j-1,list.get(j));
            list.set(j,tmp);
        }
    }
}

Eric McIntyre•2y ago

While InsertionSort has an runtime complexity of O(n²) for the average and worst case, it performs well on small arrays (because it doesn't have much overhead) and arrays that are mostly sorted (due to it not require ring much extra effort/just looping over sorted parts). The runtime complexity for the best case (already sorted array) is O(n).

⭐ Submission from dan1st#7327

Gaming

Programming

Week 8 — How would you implement the insert sort sorting algorithm in Java?