insertion sort java insertion sort algorithm examples
このチュートリアルでは、Javaでの挿入ソートについて、そのアルゴリズム、擬似コード、配列のソート例、単一リンクリストと二重リンクリストを含めて説明します。
挿入ソートアルゴリズムの手法はバブルソートに似ていますが、少し効率的です。挿入ソートは、要素の数が少ない場合に、より実行可能で効果的です。データセットが大きい場合、データの並べ替えに時間がかかります。
Adobe FlashPlayerでSWFを開く方法
学習内容：
Javaでの挿入ソートの概要
挿入ソート手法では、リストの最初の要素がすでにソートされていると想定し、2番目の要素から始めます。 2番目の要素は最初の要素と比較され、順番になっていない場合は交換されます。このプロセスは、後続のすべての要素に対して繰り返されます。
一般に、挿入ソート手法では、各要素を前のすべての要素と比較し、要素をソートして適切な位置に配置します。
すでに述べたように、挿入ソート手法は、データセットが少ない場合に適しているため、要素数が少ない配列は、効率的な挿入ソートを使用してソートできます。
挿入ソートは、リンクリストのデータ構造をソートする場合に特に便利です。ご存知のように、リンクリストには、次の要素（単一リンクリスト）と前の要素（二重リンクリスト）を指すポインターがあります。これにより、前の要素と次の要素を追跡しやすくなります。
したがって、リンクリストの並べ替えには挿入ソートを使用する方が簡単です。ただし、データ項目が多い場合、並べ替えには時間がかかります。
このチュートリアルでは、アルゴリズム、擬似コード、および例を含む挿入ソート手法について説明します。また、挿入ソートを使用して、配列、単一リンクリスト、および二重リンクリストをソートするJavaプログラムを実装します。
挿入ソートアルゴリズム
挿入ソートのアルゴリズムは次のとおりです。
ステップ1 ：K = 1〜N-1について、手順2〜5を繰り返します。
ステップ2 ：設定温度= A (K)
ステップ3 ：J = K –1に設定
ステップ4 ：
温度を上げながら繰り返す<=A(J)
セットA (J + 1) = A (J)
J = J –1に設定します
【インナーループ終了】
ステップ5 ：
セットA (J + 1) =温度
(ループの終わり)
ステップ6 ： 出口
ご存知のように、挿入ソートは、最初の要素がすでにソートされていると仮定して、2番目の要素から始まります。上記の手順は、2番目以降のリスト内のすべての要素に対して繰り返され、目的の位置に配置されます。
挿入ソートの擬似コード
挿入ソート手法の擬似コードを以下に示します。
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element while freePosition > 0 and array(freePosition -1) > insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedure次に、挿入ソートを使用して配列をソートする方法を示す図を見てみましょう。
挿入ソートを使用した配列のソート
配列を使用した挿入ソートの例を見てみましょう。
ソートされる配列は次のとおりです。
ここで、パスごとに、現在の要素を以前のすべての要素と比較します。したがって、最初のパスでは、2番目の要素から始めます。
したがって、N個の要素を含む配列を完全にソートするには、N個のパスが必要です。
Windows10に最適なSnippingTool
上記の図は、以下に示すように表形式で要約できます。
| パス | ソートされていないリスト | 比較 | ソート済みリスト |
|---|---|---|---|
| 1 | {10,2,6,15,4,1} | {10.2} | {2,10、6,15,4,1} |
| 二 | {2,10、6,15,4,1} | {2、10、6} | {2,6,10,15,4,1} |
| 3 | {2,6,10,15,4,1} | {2.6、10.15} | {2,6,10,15,4,1} |
| 4 | {2,6,10,15,4,1} | {2.6、10.15.4} | {2,4,6,10,15,1} |
| 5 | {2,4,6,10,15,1} | {2,4,6,10,15,1} | {1,2,4,6、10,15} |
| 6 | {} | {} | {1,2,4,6、10,15} |
上の図に示すように、各パスの最後に、1つの要素が適切な場所に配置されます。したがって、一般に、N個の要素を適切な場所に配置するには、N-1パスが必要です。
Javaでの挿入ソートの実装
次のプログラムは、Javaでの挿入ソートの実装を示しています。ここでは、挿入ソートを使用してソートされる配列があります。
import java.util.*; public class Main { public static void main(String() args) { //declare an array and print the original contents int() numArray = {10,6,15,4,1,45}; System.out.println('Original Array:' + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k=0 && temp <= numArray(j)) { numArray(j+1) = numArray(j); j = j-1; } numArray(j+1) = temp; } //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(numArray)); } } 出力：
元の配列：(10、6、15、4、1、45)
ソートされた配列：(1、4、6、10、15、45)
上記の実装では、ソートは2から始まることがわかります。nd配列の要素（ループ変数j = 1）の場合、現在の要素が前のすべての要素と比較されます。次に、要素は正しい位置に配置されます。
挿入ソートは、小さい配列や、ソートが少ないパスで完了する部分的にソートされた配列に対して効果的に機能します。
挿入ソートは安定したソートです。つまり、リスト内の等しい要素の順序を維持します。
挿入ソートを使用したリンクリストのソート
次のJavaプログラムは、挿入ソートを使用した単一リンクリストのソートを示しています。
import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val 出力：
元のリンクリスト：
1 8 32 2 10
ソートされたリンクリスト：
1 2 8 10 32
上記のプログラムでは、リンクリストを作成し、それにノードを追加し、並べ替えるクラスを定義しました。単一リンクリストには次のポインタがあるため、リストを並べ替えるときにノードを追跡する方が簡単です。
挿入ソートを使用した二重リンクリストのソート
次のプログラムは、挿入ソートを使用して二重リンクリストをソートします。二重リンクリストには前のポインタと次のポインタの両方があるため、データの並べ替え中にポインタを更新して再リンクするのは簡単です。
class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args()) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( 'Original doubly linked list:'); print_DLL(head); head=insertion_Sort(head); System.out.println('
Sorted Doubly Linked List:'); print_DLL(head); } } 出力：
元の二重リンクリスト：
1 11 2 7 3 5
ソートされた二重リンクリスト：
1 2 3 5 7 11
よくある質問
Q＃1）Javaの挿入ソートとは何ですか？
Windows10でネットワークセキュリティキーを見つける方法
回答： 挿入ソートは、Javaの単純なソート手法であり、より小さなデータセットとその場で効率的です。最初の要素は常にソートされ、その後の各要素は前のすべての要素と比較され、適切な位置に配置されると想定されています。
Q＃2） 挿入ソートが優れているのはなぜですか？
回答： クイックソートのような他の手法が再帰呼び出しによってオーバーヘッドを追加する場合、挿入ソートは小さなデータセットの方が高速です。挿入ソートは、他のソートアルゴリズムよりも比較的安定しており、必要なメモリも少なくて済みます。配列がほぼソートされている場合、挿入ソートもより効率的に機能します。
Q＃3） 挿入ソートは何に使用されますか？
回答： 挿入ソートは主に、ファイル検索、パス検索、データ圧縮などの複雑なプログラムを構築するコンピューターアプリケーションで使用されます。
Q＃4）挿入ソートの効率はどれくらいですか？
回答： 挿入ソートの平均ケースパフォーマンスはO（n ^ 2）です。挿入ソートの最良のケースは、配列がすでにソートされていて、それがO（n）である場合です。挿入ソートの最悪の場合のパフォーマンスもO（n ^ 2）です。
結論
挿入ソートは、配列またはリンクリストで機能する単純なソート手法です。データセットが小さい場合に役立ちます。データセットが大きくなると、この手法は遅くなり、非効率的になります。
挿入ソートは、他のソート手法よりも安定していて、インプレースです。ソートされた要素を格納するために個別の構造が使用されないため、メモリのオーバーヘッドはありません。
挿入ソートは、単一リンクリストと二重リンクリストの両方であるリンクリストのソートでうまく機能します。これは、リンクリストがポインタを介して接続されたノードで構成されているためです。したがって、ノードの並べ替えが簡単になります。
次のチュートリアルでは、Javaでのさらに別の並べ替え手法について説明します。
=> EasyJavaトレーニングシリーズをお読みください。
推奨読書
