アルゴリズム

[C言語] 選択ソートで配列の値を降順に並び替える方法

2025-01-18更新日: 2025-01-18

選択ソートは、配列を並び替えるための基本的なアルゴリズムの一つです。C言語で選択ソートを使用して配列を降順に並び替えるには、配列の各要素を順に確認し、最大の要素を見つけて先頭に移動させる操作を繰り返します。

具体的には、外側のループで配列の先頭から末尾までを走査し、内側のループで現在の位置から配列の末尾までを走査して最大値を探します。見つけた最大値を現在の位置の要素と交換することで、配列を降順に整列させます。

目次から探す

C言語での選択ソートの実装
選択ソートの動作確認
選択ソートの応用例
まとめ

C言語での選択ソートの実装

選択ソートは、配列の要素を順番に比較し、最小または最大の要素を選んで並び替えるシンプルなソートアルゴリズムです。

ここでは、C言語を用いて配列を降順に並び替える選択ソートの実装方法を解説します。

選択ソートの基本的なコード構造

選択ソートの基本的な流れは以下の通りです。

配列の最初の要素から順に、最大の要素を探す。
見つけた最大の要素を現在の位置の要素と交換する。
次の位置に移動し、同様の操作を繰り返す。

この操作を配列の最後まで繰り返すことで、配列全体が降順に並び替えられます。

配列の初期化と入力

まず、配列を初期化し、ユーザーからの入力を受け取る部分を実装します。

#include <stdio.h>
int main() {
    int array[10]; // 配列の宣言
    int n = 10; // 配列の要素数
    // ユーザーからの入力を受け取る
    printf("10個の整数を入力してください:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &array[i]);
    }
    return 0;
}

降順に並び替えるための条件設定

降順に並び替えるためには、選択ソートの比較条件を変更します。

具体的には、現在の要素と最大の要素を比較し、最大の要素を見つけるようにします。

スワップ操作の実装

スワップ操作は、2つの要素の値を交換するために必要です。

以下のように実装します。

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

完成したコードの例

以下に、選択ソートを用いて配列を降順に並び替える完全なコードを示します。

#include <stdio.h>
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int main() {
    int array[10];
    int n = 10;
    printf("10個の整数を入力してください:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &array[i]);
    }
    // 選択ソートの実装
    for (int i = 0; i < n - 1; i++) {
        int maxIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] > array[maxIndex]) {
                maxIndex = j;
            }
        }
        swap(&array[i], &array[maxIndex]);
    }
    // 結果の表示
    printf("降順に並び替えた配列:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

10個の整数を入力してください:
5 3 8 6 2 7 4 1 9 0
降順に並び替えた配列:
9 8 7 6 5 4 3 2 1 0

このコードは、ユーザーが入力した10個の整数を降順に並び替えます。

選択ソートを用いることで、配列の要素を効率的に並び替えることができます。

選択ソートの動作確認

選択ソートの実装が正しく動作するかを確認するためには、サンプルデータを用いたテストやデバッグが重要です。

ここでは、選択ソートの動作確認の方法について解説します。

サンプルデータを用いたテスト

まず、選択ソートが正しく動作するかを確認するために、いくつかのサンプルデータを用意し、テストを行います。

以下のようなデータセットを使用すると良いでしょう。

データセット	内容例
昇順データ	1, 2, 3, 4, 5, 6, 7, 8, 9, 10
降順データ	10, 9, 8, 7, 6, 5, 4, 3, 2, 1
ランダムデータ	5, 3, 8, 6, 2, 7, 4, 1, 9, 0
同一要素データ	5, 5, 5, 5, 5, 5, 5, 5, 5, 5

これらのデータセットを用いて、選択ソートが期待通りに動作するかを確認します。

デバッグ方法と注意点

選択ソートの実装において、デバッグを行う際の注意点を以下に示します。

インデックスの範囲: ループのインデックスが配列の範囲を超えないように注意します。

特に、forループの条件を確認します。

スワップ操作: スワップ操作が正しく行われているかを確認します。

スワップ関数の引数が正しく渡されているかをチェックします。

比較条件: 降順に並び替えるための比較条件が正しいかを確認します。

if文の条件が適切であるかを見直します。

デバッグの際には、printf関数を用いて、各ステップでの配列の状態を出力することで、問題の箇所を特定しやすくなります。

実行結果の確認

選択ソートの実行結果を確認するためには、プログラムの出力が期待通りであるかをチェックします。

以下に、サンプルデータを用いた実行結果の例を示します。

10個の整数を入力してください:
5 3 8 6 2 7 4 1 9 0
降順に並び替えた配列:
9 8 7 6 5 4 3 2 1 0

この実行例では、ランダムなデータセットを入力し、選択ソートによって降順に並び替えられた結果が正しく表示されています。

各データセットに対して同様の確認を行い、すべてのケースで正しい結果が得られることを確認します。

選択ソートの応用例

選択ソートは、数値の配列だけでなく、さまざまなデータ型に応用することができます。

ここでは、文字列配列や構造体配列、リストデータへの応用例を紹介します。

文字列配列の並び替え

文字列配列を選択ソートで並び替える場合、文字列の比較にはstrcmp関数を使用します。

以下に、文字列配列を降順に並び替える例を示します。

#include <stdio.h>
#include <string.h>
void swapStrings(char *str1, char *str2) {
    char temp[100];
    strcpy(temp, str1);
    strcpy(str1, str2);
    strcpy(str2, temp);
}
int main() {
    char *array[] = {"apple", "orange", "banana", "grape", "peach"};
    int n = 5;
    // 選択ソートの実装
    for (int i = 0; i < n - 1; i++) {
        int maxIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (strcmp(array[j], array[maxIndex]) > 0) {
                maxIndex = j;
            }
        }
        swapStrings(array[i], array[maxIndex]);
    }
    // 結果の表示
    printf("降順に並び替えた文字列配列:\n");
    for (int i = 0; i < n; i++) {
        printf("%s ", array[i]);
    }
    printf("\n");
    return 0;
}

降順に並び替えた文字列配列:
peach orange grape banana apple

この例では、strcmp関数を用いて文字列を比較し、降順に並び替えています。

構造体配列の並び替え

構造体配列を選択ソートで並び替える場合、構造体の特定のメンバーを基準に比較を行います。

以下に、構造体配列を降順に並び替える例を示します。

#include <stdio.h>
typedef struct {
    char name[50];
    int score;
} Student;
void swapStudents(Student *a, Student *b) {
    Student temp = *a;
    *a = *b;
    *b = temp;
}
int main() {
    Student students[] = {{"Alice", 85}, {"Bob", 92}, {"Charlie", 78}, {"David", 90}};
    int n = 4;
    // 選択ソートの実装
    for (int i = 0; i < n - 1; i++) {
        int maxIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (students[j].score > students[maxIndex].score) {
                maxIndex = j;
            }
        }
        swapStudents(&students[i], &students[maxIndex]);
    }
    // 結果の表示
    printf("降順に並び替えた構造体配列:\n");
    for (int i = 0; i < n; i++) {
        printf("%s: %d\n", students[i].name, students[i].score);
    }
    return 0;
}

降順に並び替えた構造体配列:
Bob: 92
David: 90
Alice: 85
Charlie: 78

この例では、scoreメンバーを基準に構造体配列を降順に並び替えています。

リストデータの並び替え

リストデータを選択ソートで並び替える場合、リストの各ノードを比較し、スワップ操作を行います。

以下に、単方向リストを降順に並び替える例を示します。

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node *next;
} Node;
void swapNodes(Node *a, Node *b) {
    int temp = a->data;
    a->data = b->data;
    b->data = temp;
}
void selectionSortList(Node *head) {
    for (Node *i = head; i != NULL && i->next != NULL; i = i->next) {
        Node *maxNode = i;
        for (Node *j = i->next; j != NULL; j = j->next) {
            if (j->data > maxNode->data) {
                maxNode = j;
            }
        }
        swapNodes(i, maxNode);
    }
}
void printList(Node *head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}
int main() {
    Node *head = malloc(sizeof(Node));
    head->data = 5;
    head->next = malloc(sizeof(Node));
    head->next->data = 3;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 8;
    head->next->next->next = malloc(sizeof(Node));
    head->next->next->next->data = 6;
    head->next->next->next->next = NULL;
    printf("元のリスト:\n");
    printList(head);
    selectionSortList(head);
    printf("降順に並び替えたリスト:\n");
    printList(head);
    return 0;
}

元のリスト:
5 3 8 6 
降順に並び替えたリスト:
8 6 5 3

この例では、単方向リストのノードを選択ソートで降順に並び替えています。

リストの各ノードのデータを比較し、スワップ操作を行うことで並び替えを実現しています。

まとめ

選択ソートは、シンプルでメモリ効率の良いソートアルゴリズムであり、小規模なデータセットや教育目的に適しています。

選択ソートの基本的な実装方法や応用例を通じて、その特性と限界を理解することができました。

この記事を参考に、選択ソートを実際のプログラムに応用し、他のソートアルゴリズムとの違いを体験してみてください。