Selection Sort

I solved the problem 2.2-2 in 「Introduction to Algorithm」 written by Thomas. I wrote a selection sort using Python:

#! /usr/bin/env python
# coding:utf-8

import copy

def selection_sort(lst):
    _lst = copy.deepcopy(lst)
    for i in range(0, len(_lst) - 1):
        j = i + 1
        min_index = i
        for k in range(j, len(_lst)):
            if _lst[k] < _lst[min_index]:
                min_index = k
        if min_index != i:
            tmp_val = _lst[i]
            _lst[i] = _lst[min_index]
            _lst[min_index] = tmp_val
    return _lst

The loop invariant is

for , lst[0], lst[1], …, lst[i] are in sorted order.

This proof is easy. You can also show that this selection sort is collect by using this loop invariant. Both worst-case and best-case runnning times are .

comparison with a insertion sort

The best-case running time of insertion sort is ; however, the best-case running time of selection sort is .