【基本情報技術者試験】挿入ソートで比べる C・Go・Kotlin ～シフトと挿入、3言語で見る組み方の違い～

スポンサーリンク
C言語

前回、「挿入ソート問題をC言語のコードで確認してみよう！」でトレース問題の解き方を確認した。今回は挿入ソートをGo・Kotlinにも移植し、3言語で比べてみる。

これまでのバブルソート・選択ソートと同様、ロジックそのものは3言語で共通しつつ、ループの表現方法にどんな違いが出るかを見ていく。掲載しているコードはすべてそのままコピーして実行できる。

C言語版（おさらい）

#include <stdio.h>

#define SIZE 6

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

void insertion_sort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
        printf("%d回目のパス後: ", i);
        print_array(arr, size);
    }
}

int main(void) {
    int data[SIZE] = {5, 2, 8, 1, 9, 3};

    printf("ソート前: ");
    print_array(data, SIZE);

    insertion_sort(data, SIZE);

    printf("ソート後: ");
    print_array(data, SIZE);

    return 0;
}

実行方法

gcc -Wall -Wextra -o insertion_sort insertion_sort.c
./insertion_sort

Go版

package main

import "fmt"

func insertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		key := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > key {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = key
		fmt.Printf("%d回目のパス後: %v\n", i, arr)
	}
}

func main() {
	data := []int{5, 2, 8, 1, 9, 3}

	fmt.Println("ソート前:", data)

	insertionSort(data)

	fmt.Println("ソート後:", data)
}

実行方法

go run insertion_sort.go

Kotlin版

fun insertionSort(arr: IntArray) {
    for (i in 1 until arr.size) {
        val key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
        println("${i}回目のパス後: ${arr.joinToString(" ")}")
    }
}

fun main() {
    val data = intArrayOf(5, 2, 8, 1, 9, 3)

    println("ソート前: ${data.joinToString(" ")}")

    insertionSort(data)

    println("ソート後: ${data.joinToString(" ")}")
}

実行方法

kotlinc InsertionSort.kt -include-runtime -d insertion_sort.jar
java -jar insertion_sort.jar

実行結果

出力の書式は言語によって少し異なる（Goは[ ]で囲んで表示するなど）が、パスごとの経過・最終的なソート結果はもちろん同じになる。

C言語版

ソート前: 5 2 8 1 9 3
1回目のパス後: 2 5 8 1 9 3
2回目のパス後: 2 5 8 1 9 3
3回目のパス後: 1 2 5 8 9 3
4回目のパス後: 1 2 5 8 9 3
5回目のパス後: 1 2 3 5 8 9
ソート後: 1 2 3 5 8 9

Go版

ソート前: [5 2 8 1 9 3]
1回目のパス後: [2 5 8 1 9 3]
2回目のパス後: [2 5 8 1 9 3]
3回目のパス後: [1 2 5 8 9 3]
4回目のパス後: [1 2 5 8 9 3]
5回目のパス後: [1 2 3 5 8 9]
ソート後: [1 2 3 5 8 9]

Kotlin版

ソート前: 5 2 8 1 9 3
1回目のパス後: 2 5 8 1 9 3
2回目のパス後: 2 5 8 1 9 3
3回目のパス後: 1 2 5 8 9 3
4回目のパス後: 1 2 5 8 9 3
5回目のパス後: 1 2 3 5 8 9
ソート後: 1 2 3 5 8 9

3言語を比べてみる

key退避 → シフト → 挿入という3ステップの流れは、3言語ともまったく同じ順序で書かれている。挿入ソートは選択ソートと違って交換処理がないため、言語機能による書き方の差がほとんど出ない、というのがまず見えてくる特徴である。

while相当の書き方特徴
Cwhile (j >= 0 && arr[j] > key)そのままwhile文
Gofor j >= 0 && arr[j] > keyGoにwhile文はなく、条件だけのfor文で代用する
Kotlinwhile (j >= 0 && arr[j] > key)Cと同じくwhile文がある

ここが選択ソート編との違いである。選択ソートでは「交換の書き方」に言語差が出たが、挿入ソートではループ文そのものの語彙に差が出る。Goにはwhile文という予約語自体が存在せず、forの条件式だけを書くことで同じ動きを表現する。C・Kotlinの経験があると、最初は「while はどこ？」と探してしまうポイントである。

もう一つの共通点として、keyという一時変数を使ってシフト前の値を退避する、という発想は3言語とも変わらない。この「退避してから走査する」という考え方自体が挿入ソートの核であり、言語を変えても崩れない部分である。

FE試験のポイント

  • 試験の擬似言語ではwhile文に相当する繰り返し構文がそのまま出題される。Goのように「forでwhileを表現する」書き方は擬似言語には登場しないため、C・Kotlinの書き方の方が擬似言語との対応がとりやすい
  • key（退避用変数）の役割を問う設問では、「ループ中に配列のどこにも書き戻されていない」という性質が問われやすい。この点は言語が変わっても共通の急所である

まとめ

  • 挿入ソートはkey退避・シフト・挿入という3ステップの流れが3言語で完全に一致している
  • 選択ソートと違い、交換処理がないぶん言語機能による書き方の差は小さい
  • 唯一の大きな違いはwhile文の有無で、Goだけがforの条件式で代用する

これでバブル・選択・挿入という3つのソートについて、C・Go・Kotlinそれぞれの実装とトレース問題対応、そして3言語比較まで一区切りとなる。次回以降は、この3つのソートをまとめて振り返る記事や、より発展的なソートアルゴリズム（マージソート・クイックソートなど）を取り上げる予定である。

この記事で扱ったコードは、GitHubの c-language-studies リポジトリ （FE-algorithm/04_insertion_sort/）で公開している。

コメント

タイトルとURLをコピーしました