Insertion sort algorithm courtesy of YouTuber Joe James

[Drone4four]

Hello Pythonistas!

I’m learning the insertion sort algorithm using Joe James’ terrific YouTube tutorial.

He’s got some resources on GitHub for reference which are enormously fun to play with.

Here is one of the variations of the three insertion sort algorithm he has:

def insertion_sort(A):
   for i in range(1, len(A)):
       for j in range(i-1, -1, -1):
           if A[j] > A[j+1]:
               A[j], A[j+1] = A[j+1], A[j]
           else:
               break
A = [5,9,1,2,4,8,6,3,7]
print(A)
insertion_sort(A)
print(A)
 

Here is the correct and expected sorted output:

Output:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

I’m struggling with line five. Could someone please clarify what is going on there?

I experimented by trying to spread out that one line into two separate ones like this:

def insertion_sort_Drone4four(A):  
   for i in range(1, len(A)):
       for j in range(i-1, -1, -1):
           if A[j] > A[j+1]:
               A[j] = A[j+1]
               A[j+1] = A[j]
           else:
               break

But then the output isn’t sorted. Instead I get this:

Output:
[1, 1, 1, 2, 3, 3, 3, 3, 7]

What is going on in the original script at line 5? Also: How might you people rewrite it to spread out that line to make it easier to read for a novice such as myself?

[bowlofred]

It swaps the values assigned to the two elements. The value of each expression on the right is assigned to the respective variable on the left. Doing the same work while split up across multiple lines/statements would require a temporary variable.

# one line swap
A, B = B, A  

# your attempt
A = B
B = A  # Doesn't work, because A is already changed.  Original value of A is lost.

# how you might write this in another language
temp = B
B = A
A = temp

[deanhystad]

It is so easy to try this kind of thing out and learn by yourself.

>>> a, b = 1, 2
>>> print(a, b)
1 2
>>> a, b = b, a
>>> print(a, b)
2 1

What happens if I only have one variable and two values?

Output:
>>> c = 1, 2
>>> c
(1, 2)

Are those really numbers?

Output:
>>> sum(c)
3

I guess so.

Can I unpack the tuple with two variables on the left?

Output:
>>> x, y = c
>>> print(x, y)
1 2

Do the number of variables have to match the number of elements?

Output:
>>> c
(1, 2, 3, 4)
>>> a, b = c
Traceback (most recent call last):
  File "<pyshell#18>", line 1, in <module>
    a, b = c
ValueError: too many values to unpack (expected 2)

I guess they do. Can I use one of those placeholders like for _ in range(10)?

Output:
>>> a, _, b, _ = c
>>> print(a, b)
1 3

[perfringo]

I think that naming can be improved in this example.

IMHO this can be expressed in more pythonic way.

This sort is in-place i.e. it can be applied only to mutable data types (immutables will raise TypeError as they don't support item assignment). Out of built-in mutable data types only list (and bytearray) are accessible by index (sets are unordered and dicts have keys and not indices). So naming parameter as list_ or similar represents much better the sorting ability than A.

Instead of antipattern of range(len()) one can write this instead:

def insertion_sort(list_):
    for i, _ in enumerate(list_):
       for j in reversed(range(i)):
           current, next_ = j, j+1
           if list_[next_] < list_[current]:
               list_[current], list_[next_] = list_[next_], list_[current]
           else:
               break

The only difference is that there will be one wasted cycle at the beginning (i = 0).