snippetjavaMinor
Insertion sort in Java
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.
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
Note that an optimised
Use binary search
You can binary search for the insertion point to improve the performance even further.
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.