Insertion sort simple question

[shivajikobardan]

I am doing on java.

Code: [Select]

package com.example.demo;

public class Sortinnnn {
    public static void main(String[] args) {
        int[] resultArray = insertionSort(new int[]{2, 9, 5, 4, 8, 1, 6});
        for (int i = 0; i < resultArray.length; i++) {
            System.out.println(resultArray[i]);
        }
    }

    public static int[] insertionSort(int[] list) {
        for (int i = 1; i < list.length; i++) {
            int currentElement = list[i];
            int k;
            for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
                list[k + 1] = list[k];
            }
            list[k + 1] = currentElement;
        }
        return list;
    }
}

There is a certain step list[k+1]=list[k]. Book claims it is shifting. But here is what I do not get it.


i starts from 2nd element.

k starts from one element before i. And it goes towards -ve axis, towards zero.

list[k+1]=list[k]

assume a situation

2,1,3,4,5


Since 1<2, we need to shift.

list[1]=list[0]

2 goes to list[1] location.

Now, later after the end of kth loop, we put ith element i.e. the currentElement variable value. But book is putting again list[k+1]=currentElement.

The last value of k will be always be 0. So, list[1]=currentElement? How does this even work?

[golden_labels]

Please write topic titles that reflect the content. “Simple question” tells nothing. It makes no sense either.

In the classic insertion sort, each step of the inner loop is an element swap operation. These swap operations happen in continuous series.

Let’s consider a following example. A series of swap operations (<->) on some arbitrary array (and not even in this algorithm):

• Element 8 <-> Element 7
• Element 7 <-> Element 6
• Element 6 <-> Element 5
• Element 5 <-> Element 4

What we really did, is shifting all elements one position up and moving element 8 to the bottom. That pattern remains true for all such serial swaps.

As a consequence, instead of doing all the swaps, we may:

• Store the uppermost element (let’s call it U).
• Shift all elements up by one position.
• Set the bottom element to U (that is: the old value of the uppermost element).

Coming back to insertion sort: the above tricks allows us to replace the entire inner loop of swaps, with equivalent code that does just the three steps above. Store value, shift elements (this is what the new inner loop does), and restore the element at the bottom.


As side note. Unrelated to algorithms, but related to coding style. If function’s job is to modify its argument in-place, it’s a poor choice to also return the result of that operation. It makes a function, that modifies its argument, look and be used as one that doesn’t. Which in turns inevitably leads to errors.

[TheCalligrapher]

Now, later after the end of kth loop, we put ith element i.e. the currentElement variable value. But book is putting again list[k+1]=currentElement.

And? Why do you think this is a problem?

The last value of k will be always be 0. So, list[1]=currentElement? How does this even work?

That is incorrect.

Firstly, why "always"? The inner cycle can terminate early if the condition `list[k] > currentElement` fails. So, it does not necessarily iterate all the way to the left.

Secondly, when `k` is already zero, the `k >= 0` condition permits one extra iteration of the cycle, which will take `k` to `-1`. This is the lowest value `k` can reach. And in your original example, when processing `list[1]` (i.e. `1`), `k` will end up being `-1` specifically. The cycle will begin iteration with `k = 0`, it will iterate through `k = 0` and then stop at `k = -1`. After that it will save `currentElement` (which is `1`) into position `list[k + 1]` (i.e into `list[0]`). So, you will end up with `1, 2, 3, 4, 5`, exactly as it should be. Following the same logic, the remaining iterations will simply "resave" the remaining elements into their already occupied positions. So, the end result is `1, 2, 3, 4, 5`.

All is right with the world.

[TheCalligrapher]

In the classic insertion sort, each step of the inner loop is an element swap operation. These swap operations happen in continuous series.

That's quite arguable. Trying to "descend" the current element to its final location through a sequence of swaps blurs the boundaries between insertion sort and bubble sort too much.

The whole idea of "classic" insertion sort is to:
1. Find the proper location for the current element in the already-sorted initial (left) portion of the array,
2. Shift the tail of the sorted portion one step to the right to "open a window" for the current element
3. Drop the current element to that new location

One can use a sequence of swaps to achieve the above objectives, but there's nothing "classic" about it. Doing what the OP's quoted implementation is doing is no less "classic", if not more. Just be wary of the error in the code. I retract my initial statement about the error. Apparently, the code is fine.

[golden_labels]

Ok, it may depend on where one learned the algorithm from. I checked: Aho, Ullman, Hopcroft used swap, while both Knuth and Cormen used find-and-shift approach. I remembered it in Aho’s version, but indeed neither should get a precedence.

However it doesn’t blur the lines with bubelsort. No more than representing bubelsort with finding instead of swapping. They remain conceptually different, no matter which implementation is chosen.

[SiliconWizard]

Shifting elements can be expressed as a sequence of transpositions, so as a sequence of swaps, but it's neither natural nor efficient to do so. And I guess it's probably best not to make those poor students all confused.

For inserting an element e at position k in the array A of length n (assuming indices start at 0), you can do the following:

Code: [Select]

A[n] <- e
for i = n -1 downto k
|        swap(A[i], A[i+1])

That is not efficient in practice but it can be expressed this way.

[ledtester]

This video does a pretty good job of animating and explaing the algorithm:

Insertion Sort Animation | Algorithm | Code -- Simply Coding
https://youtu.be/E8svn2Wgri8