選択ソート O(n^2)

同じく書籍より

#とても時間がかかるが一番わかりやすいソート
#最初から順番にみていく、そのうち減っていくので
#実質 O(n x 1/2 x n)となる
#ビックオー記法では無視されるのでO(n^2)と書く

def findSmallest(arr):
    smallest = arr[0]        #最も小さい値を格納
    smallest_index  = 0 #最も小さい値のインデックスを格納
    for i in range(1, len(arr)):
        if arr[i] < smallest: #最初は配列[0]と比べている
            smallest = arr[i]
            smallest_index = i
    return smallest_index

#この関数を使って選択ソート
def selectionSort(arr):   #配列をソート
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)   #配列内で最も小さい要素を見つけ出す
        newArr.append(arr.pop(smallest)) #新しい配列に追加
    return newArr

print selectionSort([5,3,6,2,10])  #並べ替えた

結果順序よく並べ替えられた
[2,3,5,6,10]