目次から探す
挿入ソートのアルゴリズム
アルゴリズムの概要
挿入ソートは、要素を適切な位置に挿入していくことで、配列やリストを昇順または降順に並び替えるアルゴリズムです。
具体的な手順は以下の通りです。
- ソート対象の要素を1つずつ取り出します。
- 取り出した要素を、それより前の要素と比較します。
- 取り出した要素が前の要素より小さい場合、前の要素を1つずつ後ろにずらしていきます。
- 適切な位置が見つかったら、取り出した要素をその位置に挿入します。
- 1〜4の手順を、全ての要素に対して繰り返します。
擬似コードの解説
以下に、挿入ソートの擬似コードを示します。
for i = 1 to n-1
key = array[i]
j = i - 1
while j >= 0 and array[j] > key
array[j+1] = array[j]
j = j - 1
end while
array[j+1] = key
end forこの擬似コードでは、arrayという配列をソートする例を示しています。
nは配列の要素数を表します。
具体的なコードの実装方法については後述します。
線形リストの挿入ソート
挿入ソートの実装方法
線形リストに対して挿入ソートを行う場合、以下の手順で実装します。
- ソート対象の線形リストを作成します。
- ソート対象の線形リストから要素を1つずつ取り出します。
- 取り出した要素を、それより前の要素と比較します。
- 取り出した要素が前の要素より小さい場合、前の要素を1つずつ後ろにずらしていきます。
- 適切な位置が見つかったら、取り出した要素をその位置に挿入します。
- 2〜5の手順を、全ての要素に対して繰り返します。
ソートの手順の解説
線形リストに対する挿入ソートの手順は、配列の場合とほぼ同じです。
違いは、要素の挿入やずらし操作を行う際に、ポインタを使用する点です。
- ソート対象の線形リストを作成します。
- ソート対象の線形リストから要素を1つずつ取り出します。
- 取り出した要素を、それより前の要素と比較します。
- 取り出した要素が前の要素より小さい場合、前の要素を1つずつ後ろにずらしていきます。
この際、ポインタを使用して要素の位置を操作します。
- 適切な位置が見つかったら、取り出した要素をその位置に挿入します。
また、ポインタを使用して要素の位置を操作します。
- 2〜5の手順を、全ての要素に対して繰り返します。
コードの実装
以下に、線形リストに対する挿入ソートのコードの一例を示します。
#include <stdio.h>
#include <stdlib.h>
// ノードの定義
typedef struct Node {
int data;
struct Node* next;
} Node;
// 線形リストの挿入ソート関数
void insertionSort(Node** head) {
Node* sorted = NULL;
Node* current = *head;
while (current != NULL) {
Node* next = current->next;
// 適切な位置に挿入するためのポインタを探す
Node** ptr = &sorted;
while (*ptr != NULL && (*ptr)->data < current->data) {
ptr = &(*ptr)->next;
}
// currentを挿入する
current->next = *ptr;
*ptr = current;
current = next;
}
*head = sorted;
}
// 線形リストの表示関数
void printList(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
// 線形リストの作成
Node* head = (Node*)malloc(sizeof(Node));
head->data = 5;
Node* second = (Node*)malloc(sizeof(Node));
second->data = 2;
head->next = second;
Node* third = (Node*)malloc(sizeof(Node));
third->data = 8;
second->next = third;
Node* fourth = (Node*)malloc(sizeof(Node));
fourth->data = 1;
third->next = fourth;
fourth->next = NULL;
// ソート前の線形リストの表示
printf("ソート前の線形リスト: ");
printList(head);
// 挿入ソートの実行
insertionSort(&head);
// ソート後の線形リストの表示
printf("ソート後の線形リスト: ");
printList(head);
return 0;
}このコードでは、線形リストを作成し、挿入ソートを行っています。
ソート前とソート後の線形リストを表示するための関数も実装しています。
実行結果は以下の通りです。
ソート前の線形リスト: 5 2 8 1
ソート後の線形リスト: 1 2 5 8以上が、「【C言語】線形リストを挿入ソートで並び替える方法をサンプルコード付きで解説」の記事の本文です。
挿入ソートのアルゴリズムの概要や擬似コード、線形リストに対する挿入ソートの実装方法、ソートの手順の解説、そして実際のコードの実装例を紹介しました。