selection sort java selection sort algorithm examples
このチュートリアルでは、選択ソートアルゴリズム、Javaコード、Javaでの実装、およびJavaの例とともに、Javaでの選択ソートについてすべて説明します。
選択ソート手法は、配列内の最小の要素を選択して、配列の最初の要素と交換する方法です。次に、配列内の2番目に小さい要素が2番目の要素と交換され、その逆も同様です。
=> ここでJavaトレーニングチュートリアルのA〜Zを確認するには、ここをクリックしてください。
学習内容：
Javaでの選択ソート
このようにして、配列内の最小の要素が繰り返し選択され、配列全体が並べ替えられるまで適切な位置に配置されます。
選択ソートのために2つのサブ配列が維持されます。
- ソートされたサブ配列： すべての反復で、最小要素が検出され、適切な位置に配置されます。このサブ配列はソートされています。
- ソートされていないサブ配列： ソートされていない残りの要素。
選択ソートは、単純で簡単なソート手法です。この手法では、すべてのパスで最小の要素を見つけて、それを正しい位置に配置するだけです。選択ソートは、小さいデータセットを効率的にソートするため、小さいデータセットに最適です。
したがって、データのリストが大きい場合は、選択ソートはお勧めできません。
選択ソートアルゴリズム
選択ソートの一般的なアルゴリズムを以下に示します。
選択ソート（A、N）
ステップ1 ：K = 1からN-1について、手順2と3を繰り返します。
ステップ2 ：ルーチンsmallest（A、K、N、POS）を呼び出す
ステップ3 ：
A (K)をA (POS)と交換します
(ループの終わり)
ステップ4 ： 出口
ルーチン最小（A、K、N、POS）
ステップ1 ：(初期化) set minimumItem = A (K)
ステップ2 ：(初期化) POS = Kに設定
ステップ3 ：
J = K +1からN-1の場合、繰り返します
最小アイテム> Aの場合(J)
最小アイテムを設定= A (J)
POS = Jに設定
(終了した場合)
(ループの終わり)
ステップ4 ：POSを返す
ご覧のとおり、最小数を見つけるルーチンは、データセットをトラバースしているときに呼び出されます。最小の要素が見つかると、その要素は目的の位置に配置されます。
フローチャートを作成するための最良のプログラム
選択ソートの擬似コード
選択ソートアルゴリズムの擬似コードを以下に示します。
Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j) ここで、選択ソートを使用した配列のソートについて説明します。
選択ソートの例
選択ソートの例として、ソートされる次の配列について考えてみます。
以下に、図の表形式の表現を示します。
ソートされていないリスト 最小要素 ソート済みリスト {17,10,7,29,2} 二 {} {17,10,7,29} 7 {二} {17,10,29} 10 {2.7} {17.29} 17 {2,7,10） {29} 29 {2,7,10,17} {} {2,7,10,17,29}
図から、パスごとに、次に小さい要素がソートされた配列の正しい位置に配置されていることがわかります。一般に、N個の要素の配列を並べ替えるには、合計でN-1回のパスが必要です。
Javaでの選択ソートの実装
次に、選択ソートを実装するJavaプログラムのデモを行います。
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i 出力：
元の配列：(7、5、2、20、42、15、23、34、10)
ソートされた配列：(2、5、7、10、15、20、23、34、42)
上記のJavaの例では、配列内で最小の要素を繰り返し検索し、配列全体が完全に並べ替えられるまで、並べ替えられた配列に配置します。
Javaでの選択ソートリンクリスト
以下にリンクリストを示します。選択ソートを使用してソートする必要があります。これを行うには、選択ソートの再帰的アプローチを使用します。ノードのデータ部分を交換する代わりに、ノードを交換してポインターを再調整します。
したがって、リンクリストが次のように指定されている場合：
以下に示すのは、上記のソートを実装するJavaプログラムです。
// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data 出力：
元のリンクリスト：
7 9 3 5 1 11
ソート後のリンクリスト：
1 3 5 7 9 11
上記のプログラムでは、ノードのデータコンポーネントのみを並べ替えるのではなく、ノードのリンクを再調整したことに注意してください。
よくある質問
Q＃1）選択ソートはどのように機能しますか？
回答： 選択ソートは、2つのサブ配列を維持することによって機能します。ソートされていないサブ配列の最小要素は、ソートされたサブ配列の適切な位置に配置されます。次に、2番目に低い要素が適切な位置に配置されます。このように、各反復中に最小要素を選択することにより、配列全体がソートされます。
Q＃2） 選択ソートの複雑さは何ですか？
回答： 選択ソートの全体的な複雑さはO（n二）、それにより、より大きなデータセットでは非効率的なアルゴリズムになります。他のソート手法の方が効率的です。
Q＃3） 選択ソートの長所と短所は何ですか？
回答： 選択ソートはインプレースソート手法であるため、中間要素を格納するために追加のストレージを必要としません。
小さなデータ構造だけでなく、ほとんどソートされているデータセットでも効率的に機能します。
選択ソート手法の主な欠点は、データ構造のサイズが大きくなるとパフォーマンスが非常に低下することです。遅くなるだけでなく、効率も低下します。
Q＃4） 選択ソートにはいくつのスワップがありますか？
回答： 選択ソート手法では、スワップの数が最小になります。最良の場合、配列がソートされると、選択ソートのスワップの数は0になります。
バブルソートc ++アルゴリズム
Q＃5） 選択ソートは挿入ソートよりも高速ですか？
回答： 挿入ソートは、より速く、より効率的で、安定しています。選択ソートは、小さいデータセットと部分的にソートされた構造に対してのみ高速です。
結論
選択ソートは、配列をトラバースしながら最小要素を選択することによって機能する手法です。パス/反復ごとに、データセット内の次の最小要素が選択され、適切な位置に配置されます。
選択ソート手法は、データセット内の要素の数が少ない場合は効率的に機能しますが、データセットのサイズが大きくなるとパフォーマンスが低下し始めます。挿入ソートのような他の同様の技術と比較すると、非効率になります。
このチュートリアルでは、選択ソートを使用して配列とリンクリストをソートする例を実装しました。
=> すべてのJavaトレーニングシリーズを見るには、ここにアクセスしてください。
推奨読書
