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, lst, …, 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 .