3
\$\begingroup\$

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<Integer> 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<Integer> arrayToSort){
        arrayToSort.add(destination, arrayToSort.get(source));
        arrayToSort.remove(source);
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Binary search works only on sorted arrays, but the array is not sorted... rigth? \$\endgroup\$
    – Caridorc
    Aug 29 '15 at 8:12
  • \$\begingroup\$ @Caridorc The insertion is always into the sorted part of the array. After x iterations of insertion sort, the x first elements are always sorted. Which means you can use binary search within those x elements to find the next insertion point. \$\endgroup\$
    – Emily L.
    Aug 29 '15 at 11:31
  • \$\begingroup\$ Clever! +1 padpadpad \$\endgroup\$
    – Caridorc
    Aug 29 '15 at 11:32
1
\$\begingroup\$

I guess, it's fine, just a few notes:

public static void start(List<Integer> arrayToSort){
  • There should be a space before "{".
  • By using List<Integer> you're losing memory and speed when compared to int[]
  • If you work with objects, you can make it more general
  • This method starts neither this array, nor anything else.
  • It should be called sort

 private static void insert(int source, int destination, List<Integer> arrayToSort){

I'd call it insertAndRemove or simply move as this is what it does. I'd also call the argument just array as this method doesn't care what it's meant for.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.