選択ソートPython：ガイド

Python選択ソートは、リストを2つの小さなリストに分割します。 1つのリストは、ソートされた要素を表します。もう1つのリストには、ソートされていない要素が含まれています。選択ソートは、各反復で最小値または最大値を見つけ、それらの値を順序付きリストに移動します。

リストの並べ替えは、さまざまなプログラムで一般的な操作です。

この例を考えてみましょう。教師は、生徒が最近のテストでどれだけ上手くいったかについてもっと知りたいと思っています。教師は、生徒のスコアを昇順と降順で並べ替えることができます。これにより、テストの最高点と最低点を簡単に見つけることができます。

入力、選択ソート。選択ソートは、リストを昇順または降順でソートするために使用できるアルゴリズムです。

このガイドでは、Pythonで選択ソートプログラムを作成する方法について説明します。このガイド全体で例を見ていき、選択の種類の詳細を学習できるようにします。

Python選択ソートとは何ですか？

Python選択ソートは、リスト内の最小要素を繰り返し検索し、その要素をリストの特定の最後に移動します。配列が順番に並べ替えられるまで、並べ替えは続行されます。最大要素を見つけるように選択ソートを指示することもできます。どちらのアプローチもリストを並べ替えます。

選択ソートは、リストの最初の要素が最小値であると想定しています。次に、ソートはその値を2番目の要素と比較します。 2番目の要素が最小値よりも小さい場合、2番目の要素が最小値になります。

このプロセスは、リストの最後の要素に到達するまで繰り返されます。この要素に達すると、最小値がソートされていないリストの先頭に配置されます。

参加者の81％は、ブートキャンプに参加した後、自分たちの技術的な仕事の見通しについてより自信を持っていると述べました。今日のブートキャンプにマッチしましょう。

平均的なブートキャンプの卒業生は、ブートキャンプの開始から最初の仕事を見つけるまで、キャリアの移行に6か月も費やしませんでした。

Python選択ソートガイド

例を実行する以外に、選択の並べ替えについて学ぶのに良い方法はありません。生徒の成績のリストを昇順で並べ替えてみましょう。このソートされていないリストを検討してください：

73

62

61

69

まず、リストの最初の値を最小と呼びます。 。選択ソートを繰り返すたびに、最小の要素が検索され、ソートされたサブ配列に移動されます。

最小要素の並べ替えは1つのオプションです。最大要素をソートすると、選択ソートが機能します。ただし、この例では最小要素を使用しています。

次に、最小値を2番目の要素と比較します。この要素が最小値よりも小さい場合は、2番目の要素が最小値になります。

73と62を比較します。73は62より大きいため、新しい最小値は62です。次に、リストはリスト内の他のすべての数値を調べます。

• 61は62（最小値）より大きいですか？いいえ、番号を入れ替えます。最小値は61になります。
• 69は61（最小値）より大きいですか？はい、何もしません。最小滞在日数は61です。

私たちのリストは同じように見えます：

73

62

61

69

リストの最後に到達したら、リストの最初に最小移動できます：

61

73

62

69

61（最小値）がリストの先頭に移動し、他のすべての値が1つ上に移動しました。すべての要素が並べ替えられるまで、このプロセスを繰り返します。

リストを繰り返すたびに、次の結果が返されます。

1. 73、62、61、69
2. 61、73、62、69
3. 61、62、73、69
4. 61、62、69、73

選択ソートがリスト内のすべての要素をチェックすると、ソートは停止します。

ソートされたサブアレイとソートされていないサブアレイはどちらも私たちには見えません。私たちのアルゴリズムは配列を並べ替え、配列の並べ替えられていない部分を追跡します。

Pythonで選択ソートを実行する方法

これで、理論に精通しました。よくできました。大きな挑戦の時です。 Pythonで選択ソートアルゴリズムを実装します。 Python配列を取り込んで、昇順で並べ替えるプログラムを書いてみましょう。

ソート関数を定義する

まず、選択ソートを実行するPython関数を定義します。

def sortList(array):
	length = len(array)

	for item in range(length):
		minimum = item

		for i in range(item + 1, length):
			if array[i] < array[minimum]:
				minimum = i

		(array[item], array[minimum]) = (array[minimum], array[item])

まず、Python len（）メソッドを使用して、リストの長さを取得しました。次に、これを使用してPythonを開始します リスト内のすべてのアイテムをループするループ。

ループ内の反復ごとに、 minimumの値を設定します 私たちのリストの最初のアイテムになります。これは、以前のウォークスルーで行いました。最小値を設定したら、別の リスト内のすべてのアイテムを実行するループが始まります。

リスト内の各アイテムについて、アルゴリズムは最小値がそのアイテムよりも大きいかどうかをチェックします。そうである場合、何も起こりません。それ以外の場合、最小値はプログラムが読み取っている項目になります。

リスト内のすべてのアイテムをループすると、アルゴリズムは最小値をリストの先頭に移動します。その後、私たちのプログラムはトップまで続きます ループが終了します。これは、選択ソートがリストの長さに等しい回数実行されるためです。

並べ替え関数を呼び出す

プログラムを実行しても何も起こらないことに気づいたかもしれません。これは、使用する値をまだコードに指示していないためです。プログラムの下部、sortList関数の外に次のコードを追加します。

numbers = [73, 62, 61, 69]
sortList(numbers)
print("Sorted list:", numbers)

プログラムを実行すると、以下が返されます。

[61, 62, 69, 73]

私たちのリストはソートされています。背中を軽くたたいてください。やった！

選択ソートを使用して、リストを降順でソートできます。この方法でリストを並べ替える場合は、選択ソートの「if」ステートメントを次のように変更できます。

if array[i] > array[minimum]:

小なり記号を大なり記号に変更しました。最小値がリストの最大値に設定されるため、これによりリストが降順で並べ替えられます。技術的には、最小 値は最大になります 値。

選択ソートはいつ使用する必要がありますか？

バブルソートのような選択ソートは、小さなリストに最適です。これは、アルゴリズムが大きなリストで使用される場合、挿入ソートなどの他のアルゴリズムほど効率的ではないためです。

選択ソートは、ソートアルゴリズムを始めたばかりのときに学ぶのに最適なソートです。他の種類を習得するのは難しい場合がありますが、選択の種類を明確に理解すると、さまざまな種類のリストを理解するのに役立ちます。

選択ソートの複雑さは何ですか？

選択ソートの時間計算量はO（n2）です。これは、リストに含まれる要素の数に応じて、アルゴリズムの複雑さが指数関数的に増大することを意味します。

O（n2）は、このアルゴリズムの最悪の場合、平均、および最良の場合の複雑さです。複雑さの並べ替えについて詳しく知りたい場合は、BigONotationのガイドをご覧ください。

結論

選択ソートは、データをソートするための重要な方法です。選択ソートは、リスト内のすべてのアイテムを読み取り、反復ごとに、最小のアイテムをリストの先頭に移動します。これは、リスト内のすべてのアイテムが読み取られるまで発生します。

使用するより効率的なアルゴリズムがあるため、選択ソートは教育以外では広く使用されていません。そうは言っても、それらは挿入やマージソートなどの他のソートを学ぶための良い出発点です。

Pythonについてもっと知りたいですか？知識を深めるのに役立つ専門家のアドバイスについては、Pythonの完全な学習方法ガイドをお読みください。