Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 24

25日間でC言語をマスターしよう Advent Calendar 2025

@edamame2525

【C言語】ソートアルゴリズム

Last updated at Posted at 2025-12-23

はじめに

この記事について

「C言語の基礎を学ぼう」をテーマに、自身の知識 + α をアドベントカレンダーにまとめます。
25日間でC言語をマスターしよう - Qiita Advent Calendar 2025 - Qiita

こんな方を対象としています

  • コンピュータがプログラムをどのように動かしているか知りたい／知らない方

  • プログラミングをしてみたい方

  • C言語初心者の方

キーワード

  • 選択ソート
  • 挿入ソート
  • バブルソート
  • クイックソート

説明

ソート

ソート とは並び替えのことです。
比較的簡単なソートアルゴリズム「選択ソート」「挿入ソート」「バブルソート」と、
高速なソートアルゴリズムのひとつ「クイックソート」について説明します。

選択ソート

選択ソートのアルゴリズムは下記です。

  1. 配列の中で一番小さい値を見つける
  2. 一番小さい値を1つ目の要素の値と入れ替える
    （1つ目の要素がソート済み）
  3. 残りの配列の中で一番小さい値を見つける
  4. 一番小さい値を2つ目の要素の値と入れ替える
    （2つ目の要素がソート済み）
  5. 上記のように、 最後-1 の要素まで繰り返す

5つの要素であれば、下記のようにソートが進みます。

   4 2 5 3 1
-> 1 2 5 3 4 // 1番目と5番目を交換
-> 1 2 5 3 4 // 2番目が最小なので交換しない
-> 1 2 3 5 4 // 3番目と4番目を交換
-> 1 2 3 4 5 // 4番目と5番目を交換

挿入ソート

挿入ソートのアルゴリズムは下記です。

  1. 1つ目の要素を ソート済み とする
  2. 2つ目の要素をソート済みの配列の先頭から順に比較し、適切な挿入位置を見つける
  3. その位置以降のソート済みの要素を1つずつ右にずらし、2つ目の要素を挿入する。
    （2つ目の要素がソート済み）
  4. 上記のように、 最後の要素まで繰り返す

5つの要素であれば、下記のようにソートが進みます。

   4 2 5 3 1
-> 2 4 5 3 1 // 「2」を1番目に挿入
-> 2 4 5 3 1 // 「5」を3番目に挿入（変化しない）
-> 2 3 4 5 1 // 「3」を2番目に挿入
-> 1 2 3 4 5 // 「1」を1番目に挿入

バブルソート

バブルソートのアルゴリズムは下記です。

  1. 1つ目の要素と2つ目の要素を比較し、ソート順が正しくなければ交換する
  2. 2つ目の要素と3つ目の要素を比較し、ソート順が正しくなければ交換する
  3. 同様に最後の要素まで繰り返すと、最後の要素は ソート済み となる
  4. 上記の操作を1つ目の要素から 最後-1 の要素まで繰り返す
    （最後-1 の要素がソート済み）
  5. 上記の操作を1つ目の要素から 最後-2 の要素まで繰り返す
    （最後-2 の要素がソート済み）
  6. 同様に2つ目の要素まで繰り返す

5つの要素であれば、下記のようにソートが進みます。

   4 2 5 3 1
-> 2 4 3 1 5 // 「5」が 最後   の要素となる
-> 2 3 1 4 5 // 「4」が 最後-1 の要素となる
-> 2 1 3 4 5 // 「3」が 最後-2 の要素となる
-> 1 2 3 4 5 // 「2」が 最後-3 の要素となる

クイックソート

高速なソートアルゴリズムのひとつにクイックソートがあります。
クイックソートのアルゴリズムは下記です。

  1. 配列の中から ピボット (pivot) と呼ばれる基準値を選ぶ
  2. ピボットより小さな値を左側に、大きな値を右側に移動させる
  3. 左側の区間で上記のピボット選択と移動を行う
  4. 右側の区間で上記のピボット選択と移動を行う
  5. この操作を区間の要素が1つになるまで繰り返す

7つの要素であれば、下記のようにソートが進みます。
簡単化のためにピボットは配列の末尾を選択します。

   4 2 5 7 1 6 3 // ピボットに「3」を選択
-> 2 1 3 7 4 6 5 // ピボットより小さい値を左側、大きい値を右側へ
                 // （ピボットの「3」がソート済み）
-> 1 2 3 7 4 6 5 // 左側の区間で同様の操作
                 // （ピボットの「1」がソート済み）
                 // （要素1つの区間「2」がソート済み）
-> 1 2 3 4 5 6 7 // 右側の区間で同様の操作
                 // （ピボットの「5」がソート済み）
                 // （要素1つの区間「4」がソート済み）
-> 1 2 3 4 5 6 7 // 右側の右側の区間で同様の操作
                 // （ピボットの「7」がソート済み）
                 // （要素1つの区間「6」がソート済み）

動作速度はピボットの選び方に依存します。
区間の分け方が半分になるようなピボットが理想です。

練習

1. 選択ソート、挿入ソート、バブルソート

選択ソート、挿入ソート、バブルソートをそれぞれ実装しよう。

*** 選択ソート ***
8 3 4 7 1 6 2 9 5 
1 2 3 4 5 6 7 8 9 
*** 挿入ソート ***
8 3 4 7 1 6 2 9 5 
1 2 3 4 5 6 7 8 9 
*** バブルソート ***
8 3 4 7 1 6 2 9 5
1 2 3 4 5 6 7 8 9

ポイント

どのソートも二重ループで実装できます。
繰り返し処理の条件と、値を入れ替える条件に気を付けましょう。

解答例

#include <stdio.h>

#define ARRAY_SIZE 9

void selection_sort(int *array, int size);
void insertion_sort(int *array, int size);
void bubble_sort(int *array, int size);

void print_array(int *array, int size);
void swap(int *array, int el_num1, int el_num2);

int main(void) {
    int array1[ARRAY_SIZE] = { 8, 3, 4, 7, 1, 6, 2, 9, 5 };
    int array2[ARRAY_SIZE] = { 8, 3, 4, 7, 1, 6, 2, 9, 5 };
    int array3[ARRAY_SIZE] = { 8, 3, 4, 7, 1, 6, 2, 9, 5 };

    printf("*** 選択ソート ***\n");
    print_array(array1, ARRAY_SIZE);
    selection_sort(array1, ARRAY_SIZE);
    print_array(array1, ARRAY_SIZE);

    printf("*** 挿入ソート ***\n");
    print_array(array2, ARRAY_SIZE);
    insertion_sort(array2, ARRAY_SIZE);
    print_array(array2, ARRAY_SIZE);

    printf("*** バブルソート ***\n");
    print_array(array3, ARRAY_SIZE);
    bubble_sort(array3, ARRAY_SIZE);
    print_array(array3, ARRAY_SIZE);

    return 0;
}

void selection_sort(int *array, int size) {
    int i, j, temp_min_el_num;
    for (i = 0; i < size - 1; i++) {
        temp_min_el_num = i;
        for (j = i; j < size; j++) {
            if (array[j] < array[temp_min_el_num]) {
                temp_min_el_num = j;
            }
        }
        swap(array, i, temp_min_el_num);
    }
}

void insertion_sort(int *array, int size) {
    int i, j, target_el_val;
    for (i = 1; i < size; i++) {
        target_el_val = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (array[j] > target_el_val) {
                // 要素を右へずらす
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = target_el_val;
    }
}

void bubble_sort(int *array, int size) {
    int i, j;
    for (i = 0; i < size - 1; i++) {
        for (j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
}

void print_array(int *array, int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int *array, int el_num1, int el_num2) {
    int temp = array[el_num1];
    array[el_num1] = array[el_num2];
    array[el_num2] = temp;
}

*** 選択ソート ***
8 3 4 7 1 6 2 9 5 
1 2 3 4 5 6 7 8 9 
*** 挿入ソート ***
8 3 4 7 1 6 2 9 5 
1 2 3 4 5 6 7 8 9 
*** バブルソート ***
8 3 4 7 1 6 2 9 5
1 2 3 4 5 6 7 8 9

2. クイックソート

クイックソートを実装しよう。

8 3 4 7 1 6 2 9 5 
1 2 3 4 5 6 7 8 9

ポイント

再帰関数で定義します。
左側と右側に分けたあと、それぞれに対してまたクイックソートを実行します。

解答例

#include <stdio.h>

#define ARRAY_SIZE 9

void quick_sort(int *array, int start, int end);

void print_array(int *array, int size);
void swap(int *array, int el_num1, int el_num2);

int main(void) {
    int array[ARRAY_SIZE] = { 8, 3, 4, 7, 1, 6, 2, 9, 5 };

    print_array(array, ARRAY_SIZE);
    quick_sort(array, 0, ARRAY_SIZE - 1);
    print_array(array, ARRAY_SIZE);

    return 0;
}

void quick_sort(int *array, int start, int end) {
    if (start >= end) return; // 再帰終了条件

    int pivot = array[end];

    int left = start; // 左側の要素のインデックス
    int target;
    for (target = left; target <= end; target++) {
        if (array[target] < pivot) {
            swap(array, left, target);
            left++;
        }
    }
    // 最後にピボットを右側の要素の先頭と入れ替える
    swap(array, left, end);

    quick_sort(array, start, left - 1);
    quick_sort(array, left + 1, end);
}

void print_array(int *array, int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void swap(int *array, int el_num1, int el_num2) {
    int temp = array[el_num1];
    array[el_num1] = array[el_num2];
    array[el_num2] = temp;
}

8 3 4 7 1 6 2 9 5 
1 2 3 4 5 6 7 8 9

3. ソート速度の計測

作成した各ソートにかかる時間を計測しよう。

ポイント

時間の計測は下記のように time.h を利用します。

#include <stdio.h>
#include <time.h>

int main(void) {
    clock_t start_time, end_time;

    start_time = clock(); // 開始時刻
    // 処理
    end_time = clock(); // 終了時刻

    printf("実行時間: %f 秒\n",
        ((double)(end_time - start_time)) / CLOCKS_PER_SEC); // 秒換算

    return 0;
}

解答例

各ソートの実装は前の設問のものをそのまま使用しているため、省略します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE 100000

void selection_sort(int *array, int size);
void insertion_sort(int *array, int size);
void bubble_sort(int *array, int size);
void quick_sort(int *array, int start, int end);

void swap(int *array, int el_num1, int el_num2);
void print_time(clock_t start, clock_t end);

int main(void) {
    int array1[ARRAY_SIZE];
    int array2[ARRAY_SIZE];
    int array3[ARRAY_SIZE];
    int array4[ARRAY_SIZE];
    int i;
    clock_t start_time, end_time;

    srand((unsigned int)time(NULL));

    for (i = 0; i < ARRAY_SIZE; i++) {
        array1[i] = array2[i] = array3[i] = array4[i] = rand() % ARRAY_SIZE;
    }

    start_time = clock();
    selection_sort(array1, ARRAY_SIZE);
    end_time = clock();
    print_time(start_time, end_time);

    start_time = clock();
    insertion_sort(array2, ARRAY_SIZE);
    end_time = clock();
    print_time(start_time, end_time);

    start_time = clock();
    bubble_sort(array3, ARRAY_SIZE);
    end_time = clock();
    print_time(start_time, end_time);

    start_time = clock();
    quick_sort(array4, 0, ARRAY_SIZE - 1);
    end_time = clock();
    print_time(start_time, end_time);

    return 0;
}

void print_time(clock_t start, clock_t end) {
    printf("実行時間: %f 秒\n", ((double)(end - start)) / CLOCKS_PER_SEC);
}

実行時間: 3.691000 秒
実行時間: 2.543000 秒
実行時間: 17.874000 秒
実行時間: 0.009000 秒

バブルソートは交換を繰り返すため非常に低速であり、クイックソートは非常に高速であることがわかります。

おわりに

どの言語も sort() などと記載すればソートすることが可能なため、ソートを自身で作成することは少ないかと思います。
複数あるソートアルゴリズムのうち、どれを使うか判断できると素敵ですね。

参考文献

↓↓↓ はじめてプログラミングを学んだときに読んだ本です ↓↓↓
詳細（プログラミング入門　C言語）｜プログラミング｜情報｜実教出版

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?