少し前に、「選択ソート問題を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 selection_sort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
printf("%d回目のパス後: ", i + 1);
print_array(arr, size);
}
}
int main(void) {
int data[SIZE] = {5, 2, 8, 1, 9, 3};
printf("ソート前: ");
print_array(data, SIZE);
selection_sort(data, SIZE);
printf("ソート後: ");
print_array(data, SIZE);
return 0;
}
実行方法
gcc -Wall -Wextra -o selection_sort selection_sort.c
./selection_sort
Go版
package main
import "fmt"
func selectionSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
minIdx := i
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIdx] {
minIdx = j
}
}
if minIdx != i {
arr[i], arr[minIdx] = arr[minIdx], arr[i]
}
fmt.Printf("%d回目のパス後: %v\n", i+1, arr)
}
}
func main() {
data := []int{5, 2, 8, 1, 9, 3}
fmt.Println("ソート前:", data)
selectionSort(data)
fmt.Println("ソート後:", data)
}
実行方法
go run selection_sort.go
Kotlin版
fun selectionSort(arr: IntArray) {
for (i in 0 until arr.size - 1) {
var minIdx = i
for (j in i + 1 until arr.size) {
if (arr[j] < arr[minIdx]) {
minIdx = j
}
}
if (minIdx != i) {
val temp = arr[i]
arr[i] = arr[minIdx]
arr[minIdx] = temp
}
println("${i + 1}回目のパス後: ${arr.joinToString(" ")}")
}
}
fun main() {
val data = intArrayOf(5, 2, 8, 1, 9, 3)
println("ソート前: ${data.joinToString(" ")}")
selectionSort(data)
println("ソート後: ${data.joinToString(" ")}")
}
実行方法
kotlinc SelectionSort.kt -include-runtime -d selection_sort.jar
java -jar selection_sort.jar
実行結果
出力の書式は言語によって少し異なる（Goは[ ]で囲んで表示するなど）が、パスごとの経過・最終的なソート結果はもちろん同じになる。
C言語版
ソート前: 5 2 8 1 9 3
1回目のパス後: 1 2 8 5 9 3
2回目のパス後: 1 2 8 5 9 3
3回目のパス後: 1 2 3 5 9 8
4回目のパス後: 1 2 3 5 9 8
5回目のパス後: 1 2 3 5 8 9
ソート後: 1 2 3 5 8 9
Go版
ソート前: [5 2 8 1 9 3]
1回目のパス後: [1 2 8 5 9 3]
2回目のパス後: [1 2 8 5 9 3]
3回目のパス後: [1 2 3 5 9 8]
4回目のパス後: [1 2 3 5 9 8]
5回目のパス後: [1 2 3 5 8 9]
ソート後: [1 2 3 5 8 9]
Kotlin版
ソート前: 5 2 8 1 9 3
1回目のパス後: 1 2 8 5 9 3
2回目のパス後: 1 2 8 5 9 3
3回目のパス後: 1 2 3 5 9 8
4回目のパス後: 1 2 3 5 9 8
5回目のパス後: 1 2 3 5 8 9
ソート後: 1 2 3 5 8 9
3言語を比べてみる
外側・内側ループの構造、min_idxを更新していく流れは3言語とも完全に同じである。違いが出るのは「交換処理」の書き方だけである。
| 交換の書き方 | 特徴 | |
|---|---|---|
| C | tempに退避してから3行で交換 | 最も明示的。仕組みがそのまま見える |
| Go | arr[i], arr[minIdx] = arr[minIdx], arr[i] | 多重代入で1行に収まる。tempが不要 |
| Kotlin | tempに退避してから3行で交換 | Cと同じ書き方。Kotlinにも多重代入はない |
Goは多重代入（tuple assignment）を言語仕様として持っているため、交換処理がそのまま1行で書ける。一方Kotlinは、変数の一括代入という点ではCと同じ発想が必要になる。「交換のロジックは同じでも、言語機能によって書き方が変わる」という点が、選択ソートの3言語比較で最もわかりやすい違いである。
もう一つの共通点は、ループ変数の範囲指定である。CとGoはC由来のfor (初期化; 条件; 更新)という書き方をそのまま使うが、Kotlinは0 until arr.size - 1のような範囲式を使う。境界条件（size - 1まで、i + 1から）を書き間違えやすい選択ソートにおいては、Kotlinの範囲式の方が意図を読み取りやすいと感じる。
FE試験のポイント
- 試験の擬似言語では交換処理は基本的にtemp変数を使う書き方で出題される。Goの多重代入のような省略形は登場しないため、擬似言語を読むときはC・Kotlinの書き方をベースに考えるとよい
- min_idxの更新条件（
arr[j] < arr[min_idx]）自体は言語が変わっても同じであり、ロジックの理解は1つの言語で済ませておけば他言語にもそのまま応用できる
まとめ
- 選択ソートのロジックは3言語で完全に共通しており、違いは主に交換処理の書き方に現れる
- Goの多重代入はCやKotlinにはない機能で、コードの簡潔さに直結する
- 境界条件の書き方は、Kotlinの範囲式の方が意図が伝わりやすい場面もある
次回は挿入ソートを同じ3言語で比較する。挿入ソートはシフト処理があるため、選択ソートとはまた違った視点の比較になりそうである。
この記事で扱ったコードは、GitHubの c-language-studies リポジトリ （FE-algorithm/03_selection_sort/）で公開している。
コメント