挿入ソート

my_insertion_sort.py

# coding: utf-8
import random

def my_insertion_sort(nums):
    for i in range(len(nums)-1):
        num = False
        idx = -1

        target = i + 1
        for j in range(target):
            # 対象より大きい、かつその中で1番小さい値を決定する
            if (nums[target] < nums[j] and (num == False or nums[j] < num)):
                idx = j
                num = nums[j]

        if (idx != -1):
            nums.insert(idx, nums[target])
            # 対象より前に挿入されるため、1つずれる
            del nums[target+1]

        print nums
    return nums

if __name__ == '__main__':
    nums = range(10)
    random.shuffle(nums)
    print nums
    my_insertion_sort(nums)

$ python my_insertion_sort.py
[8, 1, 2, 3, 4, 0, 9, 7, 5, 6]
[1, 8, 2, 3, 4, 0, 9, 7, 5, 6]
[1, 2, 8, 3, 4, 0, 9, 7, 5, 6]
[1, 2, 3, 8, 4, 0, 9, 7, 5, 6]
[1, 2, 3, 4, 8, 0, 9, 7, 5, 6]
[0, 1, 2, 3, 4, 8, 9, 7, 5, 6]
[0, 1, 2, 3, 4, 8, 9, 7, 5, 6]
[0, 1, 2, 3, 4, 7, 8, 9, 5, 6]
[0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]