Appropriate insertion sorting algorithm

Question

I am learning data structures, and have written an algorithm for insertion sort after learning from some sources. But I am confused which implementation is more correct or appropriate.

Code #1 This implementation takes an element and sorts itself with all the elements to its left, one by one, like bubble sort I think. I am just sorting and I think I can not say I am inserting an element to its correct location.

public static int[] insertionSortAsc(int[] elemArr){
    int len = elemArr.length;
    int temp;
    for (int i=0; i<= (len-2); i++){
        for (int j=(i+1); j>0; j--){
            if (elemArr[j] < elemArr[j-1]){
                //swap
                temp = elemArr[j];
                elemArr[j] = elemArr[j-1];
                elemArr[j-1] = temp;
            }
        }
    }
    return elemArr;
}

Code #2 This implementation takes an element into a 'temp' variable, compares it with left elements in the array and sorts them by comparing with the 'temp' element. When sorting stops, which means that the left side is sorted corresponding the 'temp' element, then this is element is put into that last location.

public static int[] insertionSort(int[] elements) {
        for (int i=1; i<elements.length; i++) {
            int j, elem_i = elements[i];
            for (j=i; j>0 && elements[j-1] > elem_i; j--) {
                elements[j] = elements[j-1];
            }
            elements[j] = elem_i;
        }
        return elements;
    }

I also have another idea though I have not written the code which I think matches my thought about the meaning of insertion sort.

1. Create an array, sortArr, of same size as that of input array.
2. Find the minimum element, and put that to sortArr[0]. If more elements with same value, put them into successive locations and maintain the count, means the index to which value is filled into sortArr. Put this minimum element to some tempMin variable.
3. Now check for another element in the original array which is just greater than tempMin, if found, replace the value of tempMin with this value, and then copy this to sortArr according to the filling count variable, increase the count thereby.
4. Repeat steps 2 and 3, until filling count variable reaches array length.
5. Exit.

I might be wrong but that is my thought. Please suggest algorithm modifications or my thinking if I am wrong.

Answer 1

Bubble or Insert?

#1 and #2 are both implementations of insertion sort (*). The way you insert the element is not so important: whether you copy one by one, use arraycopy, or bubble it down is up to implementation. I'd imagine arraycopy to be the best for larger inputs.

#3 would be closer to selection sort, a relative of insertion sort, though there's no advantage in allocating a new array. (Or maybe I misunderstand.)

Both build a sorted part in the array, guaranteeing that at step i, array[0..i] is sorted. Both do their sorting in-line, not requiring extra array allocations. And both select an element from the unsorted part and then insert it. The difference between insertion and selection is in how they select the next element to be inserted.

Insertion sort doesn't care which element is next, so it selects whichever.

Selection sort specifically select the littlest element from the rest of the array. This makes it more costly, but adds the additional guarantee that not only is array[0..i] in order, but it also contains the littlest elements of the entire array.

_{(*) Though #1 is related to bubble sort in a way his parents won't talk about.}

Optimise?

A strong point of insertion sort is that it performs very well for input that is already (mostly) sorted.

#1 unconditionally runs in quadratic time: i:[0..len-2], j:[i+1..0], which is in the order of n² - n steps.

#2 is smarter about it, and doesn't run back comparing if it won't need to. This means it has the potential to run in close to linear time. Specifically, it will be in the order of n + d*n steps, with d being the number of elements out of order.

#1 can be 'fixed' with a simple addition:

for (...) { 
    for (...) {
        if (cond) {
            swap;
        } else {
            break; // <-- 
        }
    }
}

... or, depending on your style preference:

for (...) { 
    for (... && cond) { // <-- as in #2
        if (cond) {
            swap;
        }
    }
}

... after which it's pretty much the same as #2.