Python

選択ソート O(n^2)

More than 1 year has passed since last update.

同じく書籍より


#とても時間がかかるが一番わかりやすいソート
#最初から順番にみていく、そのうち減っていくので
#実質 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]