Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is what I wrote for insertion sort in python. But somehow I'm feeling that it's between bubble and insertion sort.

def insertionSort(lst):
    for i in range(1, len(lst)):
        if lst[i] < lst[i-1]:
            for j in range(i):
                if lst[i] < lst[j]:
                    lst[i], lst[j] = lst[j], lst[i]
    return lst

if __name__ == '__main__':
    lst = [64, 88, 51, 65, 90, 75, 34, 79, 46, 36]
    print insertionSort(lst)
share|improve this question

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)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.