HiveBrain v1.2.0
Get Started
← Back to all entries
snippetjavaMinor

Insertion sort in Java

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
insertionsortjava

Problem

I've written a stable implementation of insertion sort, that sorts an array in ascending order.

Please let me know of any improvements/optimisations that can be made.

import java.util.List;

public class InsertionSort {
    public static void start(List arrayToSort){
        for(int i = arrayToSort.size() - 1; i > 0; i--){    // i is the leftmost index of sorted elements
            // j is the index at which the new element inserted in the sorted part of the array
            for(int j = arrayToSort.size() - 1; j >= i; j--){
                if(arrayToSort.get(i - 1) > arrayToSort.get(j)){
                    insert(i - 1, j + 1, arrayToSort);
                    break;
                }
            }
        }
    }

    private static void insert(int source, int destination, List arrayToSort){
        arrayToSort.add(destination, arrayToSort.get(source));
        arrayToSort.remove(source);
    }
}

Solution

Unnecessary work

Consider a list of \$n\$ elements, then insert(1,0) will move approximately \$2n\$ elements in the array when all it really had to do was swap the two elements.

Note that an optimised insert(source, destination) only needs to move source - destination elements. As this looks like self-learning or possibly homework, I'll leave the details to you.

Use binary search

You can binary search for the insertion point to improve the performance even further.

Context

StackExchange Code Review Q#85793, answer score: 2

Revisions (0)

No revisions yet.