この記事では、C言語を使ってデータを降順に並び替える方法を学びます。
具体的には、挿入ソートというシンプルで理解しやすいアルゴリズムを使って、数値や文字列、構造体の配列を降順にソートする方法を解説します。
プログラミング初心者の方でも理解しやすいように、基本的な概念から実際のコード例まで丁寧に説明しますので、ぜひ最後までご覧ください。
挿入ソートとは
挿入ソートは、ソートアルゴリズムの一つで、データを一つずつ取り出して適切な位置に挿入することで並び替える手法です。
シンプルで理解しやすいアルゴリズムであり、小規模なデータセットに対しては非常に効率的です。
挿入ソートの基本概念
挿入ソートは、未ソートの部分から要素を一つずつ取り出し、それを既にソートされた部分の適切な位置に挿入することで動作します。
具体的には、以下の手順で進行します：
- 配列の最初の要素をソート済みと見なす。
- 次の要素を取り出し、ソート済み部分の適切な位置に挿入する。
- これを配列の最後の要素まで繰り返す。
挿入ソートの特徴
挿入ソートには以下のような特徴があります：
- シンプルな実装：アルゴリズムが直感的で理解しやすく、実装も簡単です。
- 安定性：同じ値の要素の順序が保持されるため、安定なソートアルゴリズムです。
- 適応性：既にある程度ソートされているデータに対しては非常に効率的に動作します。
安定性
挿入ソートは安定なソートアルゴリズムです。
これは、同じ値を持つ要素の相対的な順序がソート後も保持されることを意味します。
例えば、元の配列において同じ値を持つ要素が複数存在する場合、挿入ソートを適用してもその順序は変わりません。
時間計算量
挿入ソートの時間計算量は以下の通りです：
- 最良の場合：O(n) – 配列が既にソートされている場合、各要素はそのままの位置に挿入されるため、線形時間で済みます。
- 平均の場合：O(n^2) – 一般的なケースでは、各要素を挿入するために平均して配列の半分を探索する必要があります。
- 最悪の場合：O(n^2) – 配列が逆順にソートされている場合、各要素を挿入するために全ての要素を探索する必要があります。
空間計算量
挿入ソートの空間計算量はO(1)です。
これは、ソートを行うために追加のメモリをほとんど必要としないことを意味します。
配列内で直接要素を移動させるため、非常にメモリ効率が良いアルゴリズムです。
挿入ソートはそのシンプルさと効率性から、特に小規模なデータセットや部分的にソートされたデータセットに対して有用です。
次のセクションでは、具体的に降順に並び替える方法について詳しく解説します。
降順ソートのアルゴリズム
昇順ソートとの違い
挿入ソートは、基本的には昇順ソートを前提に説明されることが多いですが、降順ソートも同じアルゴリズムを少し変更するだけで実現できます。
昇順ソートでは、各要素を前の要素と比較して小さい場合に挿入しますが、降順ソートでは逆に大きい場合に挿入します。
降順ソートの手順
降順ソートの手順は以下の通りです：
- 配列の2番目の要素から始めます。
- 現在の要素を一時的に保存します。
- 保存した要素を前の要素と比較し、前の要素が小さい場合は前の要素を後ろに移動します。
- 比較が終了した位置に保存した要素を挿入します。
- 配列の最後までこの操作を繰り返します。
初期化
まず、配列とその長さを定義します。
以下は例です：
#include <stdio.h>
void insertionSortDescending(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// keyより小さい要素を一つ後ろに移動
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSortDescending(arr, n);
printf("降順にソートされた配列: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}挿入位置の探索
挿入位置の探索は、現在の要素を前の要素と比較することで行います。
降順ソートの場合、前の要素が現在の要素より小さい場合に前の要素を後ろに移動します。
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
j = j - 1;
}挿入操作
挿入位置が見つかったら、保存しておいた現在の要素をその位置に挿入します。
arr[j + 1] = key;このようにして、配列全体を降順に並び替えることができます。
次に、応用例として文字列や構造体の降順ソートについても見ていきましょう。
応用例
文字列の降順ソート
挿入ソートは数値だけでなく、文字列の並び替えにも応用できます。
ここでは、文字列の配列を降順に並び替える方法を紹介します。
まず、文字列の配列を定義し、それを降順に並び替えるための挿入ソート関数を実装します。
#include <stdio.h>
#include <string.h>
void insertionSort(char arr[][20], int n) {
int i, j;
char key[20];
for (i = 1; i < n; i++) {
strcpy(key, arr[i]);
j = i - 1;
// keyより大きい要素を一つ後ろに移動
while (j >= 0 && strcmp(arr[j], key) < 0) {
strcpy(arr[j + 1], arr[j]);
j = j - 1;
}
strcpy(arr[j + 1], key);
}
}
int main() {
char arr[][20] = {"apple", "orange", "banana", "grape", "cherry"};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("降順に並び替えた文字列:\n");
for (int i = 0; i < n; i++) {
printf("%s\n", arr[i]);
}
return 0;
}このプログラムでは、insertionSort関数を使って文字列の配列を降順に並び替えています。
strcmp関数を使って文字列の比較を行い、strcpy関数を使って文字列のコピーを行っています。
実行結果
降順に並び替えた文字列:
orange
grape
cherry
banana
apple構造体の降順ソート
次に、構造体の配列を降順に並び替える方法を紹介します。
ここでは、学生の名前と成績を持つ構造体を定義し、それを成績の降順に並び替えます。
#include <stdio.h>
#include <string.h>
typedef struct {
char name[20];
int score;
} Student;
void insertionSort(Student arr[], int n) {
int i, j;
Student key;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// keyのスコアより大きい要素を一つ後ろに移動
while (j >= 0 && arr[j].score < key.score) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
Student arr[] = {{"Alice", 85}, {"Bob", 95}, {"Charlie", 75}, {"Dave", 90}, {"Eve", 80}};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("降順に並び替えた学生の成績:\n");
for (int i = 0; i < n; i++) {
printf("%s: %d\n", arr[i].name, arr[i].score);
}
return 0;
}このプログラムでは、insertionSort関数を使って学生の成績を降順に並び替えています。
構造体のメンバであるscoreを比較して並び替えを行います。
実行結果
降順に並び替えた学生の成績:
Bob: 95
Dave: 90
Alice: 85
Eve: 80
Charlie: 75このように、挿入ソートは数値や文字列だけでなく、構造体の配列にも応用できます。
比較する基準を変えることで、さまざまなデータを効率的に並び替えることができます。
