Can this algorithm be called insertion sort or is it some other algorithm?

def insertionsort(ar):
    j = None
    for i in range(0, len(ar)):
        j = i + 1
        while j != len(ar):
            if ar[j] < ar[i]:
                ar[j], ar[i] = ar[i], ar[j]
            j += 1
    return ar

I was curious that can this way of sorting be called insertion sort, there are a few differences between my code and the original implementation. In insertion sort, we pick the keys from the virtually ‘unsorted’ sub-array and compare it to the left subarray that is sorted. My code doesn’t do that it selects the key from the left subarray and compared them to the right and if encounters an element such that the key > current_element it swaps those two. There are some similarities between my code and the original code, for one they both take O(n^2) time and the left subarray is always sorted, basically, it is how I pick the keys and the way of inserting them into their correct place is different

Any idea or opinion is always welcome, THANKS! 2.

Answer

Insertion sort takes the next value from the input, finds its insertion spot in the already sorted subarray, and then inserts it there. Some characteristics:

• the inner iteration looks for an index to which ar[i] should be moved.
• the inner iteration will be over the sorted subarray.
• the sorted subarray grows by inserting into it, not necessarily by appending to it.

Selection sort finds the minimum value in the unsorted subarray and appends it to the sorted subarray. Some characteristics:

• the inner iteration looks for a value that should be moved to a given index i.
• the inner iteration will be over the unsorted subarray.
• the sorted subarray grows by appending to it.

Verifying against these characteristics, your algorithm is not insertion sort, but more like selection sort.

Your implementation still differs a bit with standard selection sort:

• it performs multiple swaps per outer iteration, while standard selection sort performs at most one swap per outer iteration.
• it uses ar[i] to store the minimum value found so far in the unsorted subarray, while standard selection sort retains the index of where that minimum value was found.

To make a comparison, I would first suggest using more pythonic code for the inner loop. This is equivalent to what you had:

def selectionsort(ar):
    for i in range(0, len(ar)):
        for j in range(i + 1, len(ar)):
            if ar[j] < ar[i]:
                ar[j], ar[i] = ar[i], ar[j]
    return ar

Here is how that code would become standard selection sort:

def selectionsort(ar):
    for i in range(0, len(ar)):
        k = i
        for j in range(i + 1, len(ar)):
            if ar[j] < arr[k]:
                k = j  # Don't swap, just remember...
        if k > i:  # Now perform just one swap:
            ar[k], ar[i] = ar[i], ar[k]
    return ar