2013-03-08

「アルゴリズムを、はじめよう」単純選択法(選択ソート, selection sort)をPythonで書く

前回のハッシュ探索法までが探索のアルゴリズムで、今回からはソートのアルゴリズムに突入です。

12,13,11,14,10と並んでいる数字を選択ソート(selection sort)を使って昇順に並べ替える問題。

アルゴリズムを、はじめよう

第7章:単純選択法(選択ソート, selection sort)のアルゴリズム


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

def main():
    array = [12, 13, 11, 14, 10]
    for i in xrange(len(array)):
        min = i
        for j in xrange(i+1, len(array)):
            if array[j] < array[min]:
                min = j
        array[i], array[min] = array[min], array[i]
    print array

if __name__ == '__main__':
    main()

たぶんこれで合っていると思ったけど、これ書くのに3時間くらいかかった。いろんな人が書いているコードを見せてもらって何とかできました。

できてしまえば、何も難しい事はないんだけど、最初自分で考えていた時は、混乱しまくりで久しぶりに知恵熱が出ましたよ。

2段階目のforループの部分をwhileで書いてたり。

変数jがi+1なんだって事に気づけばかなり楽になりました。

こういう基本的なアルゴリズムを何度も何度も書き直して、何も考えずに手が動くようになるまでやります。最低でも10回くらいは必要かな。

それができてから次のステップの本に進みます。

0 件のコメント:

コメントを投稿