Selection Sort

Pythonで「選択ソート（Selection Sort）」

はじめに

ここでは「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の中で取り上げられている「AOJ (Aizu Online Judge」)の問題を自分で解いた際に学んだことや、こう考えれば分かりやすいと感じたことなどを自分への整理も兼ねてまとめています。
このテキストはC++で書かれているので、私のようにpythonで勉強をされている初学者の方の参考になれば幸いです。また私自身も初学者ゆえ、至らない点が多々あると思いますので、ご指摘・ご助言頂ければ喜びます。よろしくお願いします。

問題詳細

ALDS 1_2_B: Selection Sort
選択ソートで昇順に並べ替える問題です。
問題詳細は上記リンクをご参考ください

考え方

・以下の処理をN-1回繰り返す
　　1. 未ソート部分から最小の要素の位置 minj を特定する
　　2. minj の位置にある要素と未ソート部分の先頭要素を交換する

pythonコード

def SelectionSort(A, N):
    cnt=0
    for i in range(N):
        minj = i       # A[i]が未ソート部分の先頭
        for j in range(i, N):
            if A[minj] > A[j]:
                minj = j  # 未ソート部分の最小要素の位置をminjに入れる
        if minj != i:
            cnt +=1
        A[i], A[minj] = A[minj], A[i] # 未ソート部分の最小要素を未ソート部分の先頭と入れ替える
    return A, cnt

N = int(input())
A = list(map(int, input().split()))

ans, cnt = SelectionSort(A, N)

print(*A)
print(cnt)

※指数表記はどうすればよいのでしょうか、ご教示いただければ幸いです。

ポイント

・未ソート部分の最小値を未ソート部分の先頭であるA[i]に入れていくことで、未ソート部分が狭まっていきます。

・計算量はO(N^2)
（未ソートの部分の最小値を見つけるためにN-1回、N-2回、...、1回の比較演算を行います。従って合計の比較演算の回数は(N^2-N)/2）となるので、計算量はN^2に比例します）

まとめ

以上となります。間違いや改善点などございましたら、よろしくお願いいたします。