Skip to main content
broken images fixed (click 'rendered output' or 'side-by-side' to see the difference; images retrieved via Wayback Machine); for more info, see https://gist.github.com/Glorfindel83/9d954d34385d2ac2597bbe864466259f
Source Link

Your solution looks ok to me. But let's understand better how this sort method actually works.

The insertion sort, works as it follows: always maintains a sorted sublist in the lower positions of the list. Each new item is then "inserted" back into the previous sublist such that the sorted sublist is one item larger. See below how insertion sorting process works. The shaded items represent the ordered sublists as the algorithm makes each pass.

insertion sortinsertion sort
(source: interactivepython.org)

We begin by assuming that a list with one item (position 00) is already sorted. On each pass, one for each item 1 through n−1, the current item is checked against those in the already sorted sublist. As we look back into the already sorted sublist, we shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted.

stepssteps
(source: interactivepython.org)

Above, a sorted sublist of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back into the already sorted items. The first comparison against 93 causes 93 to be shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered, the shifting process stops and 31 is placed in the open position. Now we have a sorted sublist of six items.

With this being said, I'd go with this implementation:

def insertionSort(lst):
    for index in range(1, len(lst)):

        currentvalue = lst[index]
        position = index

        while position > 0 and lst[position - 1] > currentvalue:
            lst[position] = lst[position - 1]
            position = position - 1

        lst[position] = currentvalue


lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst)
print(lst)

Your solution looks ok to me. But let's understand better how this sort method actually works.

The insertion sort, works as it follows: always maintains a sorted sublist in the lower positions of the list. Each new item is then "inserted" back into the previous sublist such that the sorted sublist is one item larger. See below how insertion sorting process works. The shaded items represent the ordered sublists as the algorithm makes each pass.

insertion sort

We begin by assuming that a list with one item (position 00) is already sorted. On each pass, one for each item 1 through n−1, the current item is checked against those in the already sorted sublist. As we look back into the already sorted sublist, we shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted.

steps

Above, a sorted sublist of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back into the already sorted items. The first comparison against 93 causes 93 to be shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered, the shifting process stops and 31 is placed in the open position. Now we have a sorted sublist of six items.

With this being said, I'd go with this implementation:

def insertionSort(lst):
    for index in range(1, len(lst)):

        currentvalue = lst[index]
        position = index

        while position > 0 and lst[position - 1] > currentvalue:
            lst[position] = lst[position - 1]
            position = position - 1

        lst[position] = currentvalue


lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst)
print(lst)

Your solution looks ok to me. But let's understand better how this sort method actually works.

The insertion sort, works as it follows: always maintains a sorted sublist in the lower positions of the list. Each new item is then "inserted" back into the previous sublist such that the sorted sublist is one item larger. See below how insertion sorting process works. The shaded items represent the ordered sublists as the algorithm makes each pass.

insertion sort
(source: interactivepython.org)

We begin by assuming that a list with one item (position 00) is already sorted. On each pass, one for each item 1 through n−1, the current item is checked against those in the already sorted sublist. As we look back into the already sorted sublist, we shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted.

steps
(source: interactivepython.org)

Above, a sorted sublist of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back into the already sorted items. The first comparison against 93 causes 93 to be shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered, the shifting process stops and 31 is placed in the open position. Now we have a sorted sublist of six items.

With this being said, I'd go with this implementation:

def insertionSort(lst):
    for index in range(1, len(lst)):

        currentvalue = lst[index]
        position = index

        while position > 0 and lst[position - 1] > currentvalue:
            lst[position] = lst[position - 1]
            position = position - 1

        lst[position] = currentvalue


lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst)
print(lst)
replaced http://interactivepython.org/ with https://interactivepython.org/
Source Link

Your solution looks ok to me. But let's understand better how this sort method actually works.

The insertion sort, works as it follows: always maintains a sorted sublist in the lower positions of the list. Each new item is then "inserted" back into the previous sublist such that the sorted sublist is one item larger. See below how insertion sorting process works. The shaded items represent the ordered sublists as the algorithm makes each pass.

insertion sort http://interactivepython.org/runestone/static/pythonds/_images/insertionsort.pnginsertion sort

We begin by assuming that a list with one item (position 00) is already sorted. On each pass, one for each item 1 through n−1, the current item is checked against those in the already sorted sublist. As we look back into the already sorted sublist, we shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted.

steps http://interactivepython.org/runestone/static/pythonds/_images/insertionpass.pngsteps

Above, a sorted sublist of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back into the already sorted items. The first comparison against 93 causes 93 to be shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered, the shifting process stops and 31 is placed in the open position. Now we have a sorted sublist of six items.

With this being said, I'd go with this implementation:

def insertionSort(lst):
    for index in range(1, len(lst)):

        currentvalue = lst[index]
        position = index

        while position > 0 and lst[position - 1] > currentvalue:
            lst[position] = lst[position - 1]
            position = position - 1

        lst[position] = currentvalue


lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst)
print(lst)

Your solution looks ok to me. But let's understand better how this sort method actually works.

The insertion sort, works as it follows: always maintains a sorted sublist in the lower positions of the list. Each new item is then "inserted" back into the previous sublist such that the sorted sublist is one item larger. See below how insertion sorting process works. The shaded items represent the ordered sublists as the algorithm makes each pass.

insertion sort http://interactivepython.org/runestone/static/pythonds/_images/insertionsort.png

We begin by assuming that a list with one item (position 00) is already sorted. On each pass, one for each item 1 through n−1, the current item is checked against those in the already sorted sublist. As we look back into the already sorted sublist, we shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted.

steps http://interactivepython.org/runestone/static/pythonds/_images/insertionpass.png

Above, a sorted sublist of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back into the already sorted items. The first comparison against 93 causes 93 to be shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered, the shifting process stops and 31 is placed in the open position. Now we have a sorted sublist of six items.

With this being said, I'd go with this implementation:

def insertionSort(lst):
    for index in range(1, len(lst)):

        currentvalue = lst[index]
        position = index

        while position > 0 and lst[position - 1] > currentvalue:
            lst[position] = lst[position - 1]
            position = position - 1

        lst[position] = currentvalue


lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst)
print(lst)

Your solution looks ok to me. But let's understand better how this sort method actually works.

The insertion sort, works as it follows: always maintains a sorted sublist in the lower positions of the list. Each new item is then "inserted" back into the previous sublist such that the sorted sublist is one item larger. See below how insertion sorting process works. The shaded items represent the ordered sublists as the algorithm makes each pass.

insertion sort

We begin by assuming that a list with one item (position 00) is already sorted. On each pass, one for each item 1 through n−1, the current item is checked against those in the already sorted sublist. As we look back into the already sorted sublist, we shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted.

steps

Above, a sorted sublist of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back into the already sorted items. The first comparison against 93 causes 93 to be shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered, the shifting process stops and 31 is placed in the open position. Now we have a sorted sublist of six items.

With this being said, I'd go with this implementation:

def insertionSort(lst):
    for index in range(1, len(lst)):

        currentvalue = lst[index]
        position = index

        while position > 0 and lst[position - 1] > currentvalue:
            lst[position] = lst[position - 1]
            position = position - 1

        lst[position] = currentvalue


lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst)
print(lst)
Source Link
Grajdeanu Alex
  • 9.2k
  • 4
  • 31
  • 70

Your solution looks ok to me. But let's understand better how this sort method actually works.

The insertion sort, works as it follows: always maintains a sorted sublist in the lower positions of the list. Each new item is then "inserted" back into the previous sublist such that the sorted sublist is one item larger. See below how insertion sorting process works. The shaded items represent the ordered sublists as the algorithm makes each pass.

insertion sort http://interactivepython.org/runestone/static/pythonds/_images/insertionsort.png

We begin by assuming that a list with one item (position 00) is already sorted. On each pass, one for each item 1 through n−1, the current item is checked against those in the already sorted sublist. As we look back into the already sorted sublist, we shift those items that are greater to the right. When we reach a smaller item or the end of the sublist, the current item can be inserted.

steps http://interactivepython.org/runestone/static/pythonds/_images/insertionpass.png

Above, a sorted sublist of five items consisting of 17, 26, 54, 77, and 93 exists. We want to insert 31 back into the already sorted items. The first comparison against 93 causes 93 to be shifted to the right. 77 and 54 are also shifted. When the item 26 is encountered, the shifting process stops and 31 is placed in the open position. Now we have a sorted sublist of six items.

With this being said, I'd go with this implementation:

def insertionSort(lst):
    for index in range(1, len(lst)):

        currentvalue = lst[index]
        position = index

        while position > 0 and lst[position - 1] > currentvalue:
            lst[position] = lst[position - 1]
            position = position - 1

        lst[position] = currentvalue


lst = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertionSort(lst)
print(lst)