はじめに
基本的なソートアルゴリズムについてまとめておきます(次の4つ)。
- ヒープソート
- クイックソート
- マージソート
- バブルソート
図表メインで、ソースコードは、C言語、Java、VBA、Pythonについて記載しています。
なお、JavaとPythonは初学レベルなので、もっと良い書き方があると思われます。ご注意ください。
最後は、気になる速度比較もしておきました。結果を見て、Pythonが人気がある理由がまた少し分かりました。
<目次>
1. ヒープソート
1-1. ヒープソートのアルゴリズム概要
1-2. ヒープソートのサンプルコード
2. クイックソート
2-1. クイックソートのアルゴリズム概要
2-2. クイックソートのサンプルコード
3. マージソート
3-1. マージソートのアルゴリズム概要
3-2. マージソートのサンプルコード
4. バブルソート
4-1. バブルソートのアルゴリズム概要
4-2. バブルソートのサンプルコード
5. 速度比較
5-1. 計算量
5-2. 処理速度の計測結果
5-3. 【参考】処理時間計測のソースコード
1. ヒープソート
ヒープソートは、**二分ヒープ**の性質を利用して並べ替えを行うアルゴリズムです。
二分ヒープは、次のような木構造を取ります。
要件は「完全二分木」であることと「親要素は子要素より常に大きいか等しい構造(ヒープ構造)」であることの2つです。
二分ヒープと配列のイメージ
プログラムでは、この二分ヒープを、上の図ように配列に置き換えてコードを書くことになります。
配列の要素番号をiとすると、次の式が成り立ちます。
[親要素の番号] = (i - 1) / 2 ※/(スラッシュ)は整数の除算で小数点以下は切り捨て
[左側子要素の番号] = i * 2 + 1
[右側子要素の番号] = i * 2 + 2
1-1. ヒープソートのアルゴリズム概要
ヒープソートでは、最初に、配列を「二分ヒープ」の形にする必要があります。
そして、二分ヒープの形を維持しながら、最大値である根(ルート)を順次取り出していくことになります。
アルゴリズムの考え方は、おおよそ「基本情報技術者試験平成30年度春期午後問8」に基づいています。
以下、順に見ていきます。
1-1-1. 配列を二分ヒープに変換する方法(up-heap)
ランダムな配列を二分ヒープにするためには、「既にヒープ構造になっている二分ヒープ木に対して、下から要素を追加していく方法」を使用します。
この方法は、アップヒープ(up-heap)といい、図で見ると次のような感じです。
赤色の⑧に注目すれば、上に移動(up)していくのが分かると思います。
これを配列に当てはめると、次のような手順になります。
配列をヒープ構造に変換するイメージ
ここでは、わかりやすいように、元の配列から新しい配列に1つずつ要素を入れています。
しかし、図を見てわかるように、新しい配列を用意しなくとも、元の配列に要素を置いたまま、前から順にヒープ構造にしていくことができます。
1-1-2. 二分ヒープから並べ替えをする方法(down-heap)
二分ヒープ木では根(ルート)が最大値となります。
この根(最大値)を取り出していくことで並べ替えを進めていくことになります(この点はバブルソートに近しい)。
なお、最大値を取り除くと、二分ヒープ構造が崩れます。
ここでは、下図のように上から要素を追加する形で二分ヒープ構造に戻していきます。
この方法をダウンヒープ(down-heap)といいます。
赤色の③に注目すれば、下に移動(down)していくのが分かると思います。
動きとしては、バブルソートに近いと言えますが、ヒープソートの方が、比較数・交換数は少なくて済みますので、その分効率の良いアルゴリズムとなります。
また、ヒープソートは「元の配列に要素を置いたまま交換を繰り返すことにより並べ替えができるアルゴリズム」となります。
このようなソートアルゴリズムをIn-placeアルゴリズムといいます。In-placeアルゴリズムには、追加の記憶領域をほとんど使わないで済むという利点があります。
In-placeアルゴリズムの範疇に含まれるものには、クイックソート、バブルソートなどがあります。
1-2. ヒープソートのサンプルコード
1-2-1. C言語
<ソースコード>
#include <stdio.h>
#include <stdlib.h> // malloc関数で使用
#include <time.h> // time関数、clock関数で使用
int parent(int child) {return (child - 1) / 2;} // 親要素の要素番号を取得
int left_child(int parent) {return parent * 2 + 1;} // 左の子要素の要素番号を取得
int right_child(int parent) {return parent * 2 + 2;} // 右の子要素の要素番号を取得
void swap(int *n1, int *n2);
// ヒープソート
void heap_sort(int *nums, int numslen) {
// 配列を二分ヒープに変換する(up-heap)
for (int i = 0; i < numslen; i++) {
int j = i; // 要素番号iにある要素を二分ヒープに追加(要素番号をjに代入)
while (j > 0) { // 要素番号が0以上の場合(子要素の番号である場合)はループを継続
if (nums[j] > nums[parent(j)]) { // 追加した要素が親要素より大きい場合
swap(&nums[j], &nums[parent(j)]); // 親要素と子要素を入れ替える
j = parent(j); // jの位置を入替え後の位置(親要素のあった位置)に移動
} else {
break; // 親要素の方が大きければ入替えの必要がないので確定
}
}
}
// ソート処理(down-heap)
for (int i = numslen - 1; i > 0; i--) {
swap(&nums[0], &nums[i]); // 根(ルート)の要素を最大値として確定して配列の後方に移動
int j = 0; // 配列の先頭に来た要素をdown-heapしていく
while (left_child(j) < i) {
// 子のうち値の大きい方の配列番号をtmpに格納
int tmp = left_child(j); // 一旦左の子の要素番号を入れる
if (right_child(j) < i && nums[right_child(j)] > nums[tmp]) tmp = right_child(j); // 右の要素(値)が大きければtmpを入替え
// 親の値が子の値より小さければ入れ替え
if (nums[j] < nums[tmp]) {
swap(&nums[j], &nums[tmp]);
j = tmp;
} else {
break; // 親の値が子の値より大きければ確定
}
}
}
}
// スワップ(入れ替え)関数
void swap(int *n1, int *n2) {
int tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}
// ヒープソートの実行
int main(void) {
// ソート用の配列を作成
srand((unsigned int)time(NULL)); // 乱数の発生をランダムにする
int n = 10;
int *nums = malloc(n * sizeof(int)); // int型配列のメモリを確保
for (int i = 0; i < n; i++) nums[i] = (int)rand() % n; // ランダムな値を代入
for (int i = 0; i < n; i++) printf("%d, ", nums[i]); // ソート前の配列出力
printf("\n");
heap_sort(nums, n);
for (int i = 0; i < n; i++) printf("%d, ", nums[i]); // ソート後の配列出力
printf("\n");
return 0;
}
<出力確認>
$ gcc heap_sort.c
$ ./a.out
4, 6, 9, 7, 4, 2, 8, 0, 3, 2,
0, 2, 2, 3, 4, 4, 6, 7, 8, 9,
1-2-2. Java
<ソースコード>
import java.util.Random;
public class HeapSortTest {
public static void main(String[] args) {
// ソート用の配列を作成
int n = 10;
int nums[] = new int[n];
Random rand = new Random(); // 乱数のインスタンスを作成
for (int i = 0; i < n; i++) nums[i] = rand.nextInt(n); // ランダムな値を代入
for (int i = 0; i < nums.length; i++) System.out.print(nums[i] + ", "); // ソート前の配列出力
System.out.print("\n");
HeapSort(nums, n); // ヒープソートの実行
for (int i = 0; i < nums.length; i++) System.out.print(nums[i] + ", "); // ソート前の配列出力
System.out.print("\n");
}
public static void HeapSort(int nums[], int n) {
// 配列を二分ヒープに変換する(up-heap)
for (int i = 0; i < n; i++) {
int j = i; // 要素番号iにある要素を二分ヒープに追加(要素番号をjに代入)
while (j > 0) { // 要素番号が0以上の場合(子要素の番号である場合)はループを継続
if (nums[j] > nums[parent(j)]) { // 追加した要素が親要素より大きい場合
Swap(nums, j, parent(j)); // 親要素と子要素を入れ替える
j = parent(j); // jの位置を入替え後の位置(親要素のあった位置)に移動
} else {
break; // 親要素の方が大きければ入替えの必要がないので確定
}
}
}
// ソート処理(down-heap)
for (int i = n - 1; i > 0; i--) {
Swap(nums, 0, i); // 根(ルート)の要素を最大値として確定して配列の後方に移動
int j = 0; // 配列の先頭に来た要素をdown-heapしていく
while (left_child(j) < i) {
// 子のうち値の大きい方の配列番号をtmpに格納
int tmp = left_child(j); // 一旦左の子の要素番号を入れる
if (right_child(j) < i && nums[right_child(j)] > nums[tmp]) tmp = right_child(j); // 右の要素(値)が大きければtmpを入替え
// 親の値が子の値より小さければ入れ替え
if (nums[j] < nums[tmp]) {
Swap(nums, j, tmp);
j = tmp;
} else {
break; // 親の値が子の値より大きければ確定
}
}
}
}
public static int parent(int child) {return (child - 1) / 2;} // 親要素の要素番号を取得
public static int left_child(int parent) {return parent * 2 + 1;} // 左の子要素の要素番号を取得
public static int right_child(int parent) {return parent * 2 + 2;} // 右の子要素の要素番号を取得
public static void Swap(int nums[], int n1, int n2) {
int tmp = nums[n1];
nums[n1] = nums[n2];
nums[n2] = tmp;
}
}
<出力確認>
$ javac HeapSortTest.java
$ java HeapSortTest
2, 0, 4, 3, 3, 3, 3, 8, 9, 5,
0, 2, 3, 3, 3, 3, 4, 5, 8, 9,
1-2-3. VBA
<ソースコード>
'ヒープソート
Sub HeapSort(nums() As Long)
Dim i As Long
Dim c As Long '主に子(child)の要素番号に使用
Dim p As Long '主に親(parent)の要素番号に使用
'配列を二分ヒープに変換する(up-heap)
For i = 0 To UBound(nums)
c = i
Do While c > 0
If nums(c) <= nums(GetPNode(c)) Then Exit Do '子が親以下の値であればループを抜ける(VBAはOrでは結べない)
Call Swap(nums(c), nums(GetPNode(c)))
c = GetPNode(c)
Loop
Next
'ソート処理(down-heap)
For i = UBound(nums) To 0 Step -1
p = 0
Call Swap(nums(p), nums(i))
Do While GetLNode(p) < i
'子のうち値の大きい方の配列番号をcに格納
If GetLNode(p) = i - 1 Then '子要素が左のみであれば
c = GetLNode(p) 'cに左の子の要素番号を格納
ElseIf nums(GetLNode(p)) > nums(GetRNode(p)) Then '左の要素の値が右の要素より大きければ(VBAはOrでは結べない)
c = GetLNode(p) 'cに左の子の要素番号を格納
Else
c = GetRNode(p) 'cに右の子の要素番号を格納
End If
'親の値が子の値より小さければ入れ替え
If nums(p) >= nums(c) Then Exit Do '親が子以上の値であればループを抜ける
Call Swap(nums(p), nums(c))
p = c
Loop
Next
End Sub
'親要素の要素番号を取得
Function GetPNode(n As Long) As Long
GetPNode = (n - 1) \ 2
End Function
'左の子要素の要素番号を取得
Function GetLNode(n As Long) As Long
GetLNode = n * 2 + 1
End Function
'右の子要素の要素番号を取得
Function GetRNode(n As Long) As Long
GetRNode = n * 2 + 2
End Function
'スワップ
Sub Swap(a As Variant, b As Variant)
Dim tmp As Variant
tmp = a
a = b
b = tmp
End Sub
<出力確認>
Sub OutputHeapSoat()
Dim nums() As Long
Call CreateArray(nums, 10) '配列を作成
Call PrintArray(nums) 'ソート前の配列を出力
Call HeapSort(nums)
Call PrintArray(nums) 'ソート前の配列を出力
End Sub
'乱数による配列作成プロシージャ
Sub CreateArray(nums() As Long, n As Long)
Dim i As Long
ReDim nums(n - 1)
Randomize '乱数ジェネレーターを初期化(都度異なる乱数値を取得するため)
For i = 0 To UBound(nums)
nums(i) = Fix(Rnd * n)
Next
End Sub
'1次元配列の内容を出力するプロシージャ
Sub PrintArray(nums As Variant)
Dim i As Long
Dim buf As String
For i = 0 To UBound(nums)
buf = buf & nums(i) & ", "
Next
Debug.Print buf
End Sub
1, 1, 6, 6, 0, 6, 2, 8, 6, 9,
0, 1, 1, 2, 6, 6, 6, 6, 8, 9,
1-2-4. Python
<ソースコード>
import random
def parent(child): return (child - 1) // 2
def left_child(parent): return parent * 2 + 1
def right_child(parent): return parent * 2 + 2
# ヒープソート
def heap_sort(nums):
for i in range(len(nums)):
j = i
while j > 0:
if nums[j] > nums[parent(j)]: nums[j], nums[parent(j)], j = nums[parent(j)], nums[j], parent(j)
else: break
for i in range(len(nums) - 1, 0, -1):
nums[0], nums[i], j = nums[i], nums[0], 0
while left_child(j) < i:
tmp = left_child(j)
if right_child(j) < i and nums[right_child(j)] > nums[tmp]: tmp = right_child(j)
if nums[j] < nums[tmp]: nums[j], nums[tmp], j = nums[tmp], nums[j], tmp
else: break
# ヒープソートの実行
n = 10
nums = [random.randint(0, n - 1) for i in range(n)]
print(nums) # ソート前の配列出力
heap_sort(nums) # ヒープソート
print(nums) # ソート後の配列出力
<出力確認>
> python HeapSort.py
[0, 0, 8, 2, 3, 9, 4, 5, 0, 5]
[0, 0, 0, 2, 3, 4, 5, 5, 8, 9]
2. クイックソート
クイックソートは、その名のとおり処理速度が速いアルゴリズムです。
2-1. クイックソートのアルゴリズム概要
2-1-1. 基本となる考え方
クイックソートでは、以下の図のように、配列の中で基準となる数値を一つ決めて、基準よりも小さい値のグループと、基準以上の値のグループに分けていきます。
各グループで更にこれを繰り返すことで、並べ替えを完了させるアルゴリズムです。
クイックソートのイメージ
クイックソートもヒープソートと同様に、In-placeアルゴリズム(元の配列に要素を置いたまま交換により並べ替えをするアルゴリズム)の範疇に入ります。
2-1-2. 基準値との比較方法と要素の交換方法
クイックソートをコード化する一般的な考え方として「基本情報技術者試験平成27年度春期午後問8」があります(Wikipediaの解説も同様)が、この方法を採ると無限ループを回避する工夫が必要となるため結構面倒でした。
ここでは、こちらの論文「(MAX上における)アルゴリズム的問題におけるユーザーインターフェースの改良」で紹介されているクイックソートの考え方をベースとして次のような方法でコードを書いていきます。
クイックソートにおける要素交換方法のイメージ
以上の処理を終えた後に、更に、基準値未満の数(s
からp-1
までの要素)と、基準値以上の数(p+1
からe
までの要素)について同じ処理を再帰的に繰り返すことになります。
2-2. クイックソートのサンプルコード
2-2-1. C言語
<ソースコード>
#include <stdio.h>
#include <stdlib.h> // malloc関数で使用
#include <time.h> // time関数、clock関数で使用
void swap(int *n1, int *n2);
// クイックソート
void quick_sort(int *nums, int s, int e) {
if (s >= e) return; // 配列の要素数が1以下の場合は処理不要
int p = s; // 最終的にはこのpの位置より左側に基準値より小さい要素が並ぶ
int h = (s + e) / 2; // 基準値は配列中央から選ぶことにする
swap(&nums[s], &nums[h]); // 基準値は一旦配列先頭に置いておく(基準値=nums[s]となる)
for (int i = s + 1; i <= e; i++) {
if (nums[i] < nums[s]) swap(&nums[++p], &nums[i]); // 基準値より小さい要素をpの左側に移動させていく
}
swap(&nums[s], &nums[p]); // 基準値をpの位置に置き換える(基準値の位置が確定)
quick_sort(nums, s, p - 1); // 配列前半部分(基準値より小さい値)を再帰処理
quick_sort(nums, p + 1, e); // 配列後半部分(基準値以上の値)を再帰処理
}
// スワップ(入れ替え)関数
void swap(int *n1, int *n2) {
int tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}
// クイックソートの実行
int main(void) {
// ソート用の配列を作成
srand((unsigned int)time(NULL)); // 乱数の発生をランダムにする
int n = 10;
int *nums = malloc(n * sizeof(int)); // int型配列のメモリを確保
for (int i = 0; i < n; i++) nums[i] = (int)rand() % n; // ランダムな値を代入
for (int i = 0; i < n; i++) printf("%d, ", nums[i]); // ソート前の配列出力
printf("\n");
quick_sort(nums, 0, n - 1); // クイックソートの実行
for (int i = 0; i < n; i++) printf("%d, ", nums[i]); // ソート後の配列出力
printf("\n");
return 0;
}
<出力確認>
$ gcc quick_sort.c
$ ./a.out
3, 8, 9, 5, 0, 9, 8, 1, 2, 8,
0, 1, 2, 3, 5, 8, 8, 8, 9, 9,
参考:先頭要素を基準値とした場合
なお、リスクはありますが、並べ替えする配列がランダムなものであれば、先頭の要素をそのまま基準値として、次のように簡潔に書くこともできます。
交換回数も減るので、スピードも少し早くなります(配列の並びがランダムであれば)。
// クイックソート(先頭要素を基準値とした場合)
void quick_sort(int *nums, int s, int e) {
if (s >= e) return;
int p = s;
for (int i = s + 1; i <= e; i++) if (nums[i] < nums[s]) swap(&nums[++p], &nums[i]);
swap(&nums[s], &nums[p]);
quick_sort(nums, s, p - 1);
quick_sort(nums, p + 1, e);
}
でも、並べ替える配列が、もともと昇順に近い形である場合には、かなり無駄な演算を繰り返すことになりますので、やっぱりこの書き方はあまり適切でないと思います。
2-2-2. Java
<ソースコード>
import java.util.Random;
public class QuickSortTest {
public static void main(String[] args) {
// ソート用の配列を作成
int n = 10;
int nums[] = new int[n];
Random rand = new Random(); // 乱数のインスタンスを作成
for (int i = 0; i < n; i++) nums[i] = rand.nextInt(n); // ランダムな値を代入
for (int i = 0; i < nums.length; i++) System.out.print(nums[i] + ", "); // ソート前の配列出力
System.out.print("\n");
QuickSort(nums, 0, n - 1); // クイックソートの実行
for (int i = 0; i < nums.length; i++) System.out.print(nums[i] + ", "); // ソート前の配列出力
System.out.print("\n");
}
// クイックソート
public static void QuickSort(int nums[], int s, int e) {
if (s >= e) return; // 配列の要素数が1以下の場合は処理不要
int p = s; // 最終的にはこのpの位置より左側に基準値より小さい要素が並ぶ
int h = (s + e) / 2; // 基準値は配列中央から選ぶことにする
Swap(nums, s, h); // 基準値は一旦配列先頭に置いておく(基準値=nums[s]となる)
for (int i = s + 1; i <= e; i++) {
if (nums[i] < nums[s]) Swap(nums, ++p, i); // 基準値より小さい要素をpの左側に移動させていく
}
Swap(nums, s, p); // 基準値をpの位置に置き換える(基準値の位置が確定)
QuickSort(nums, s, p - 1); // 配列前半部分(基準値より小さい値)を再帰処理
QuickSort(nums, p + 1, e); // 配列後半部分(基準値以上の値)を再帰処理
}
// Swap関数
public static void Swap(int nums[], int n1, int n2) {
int tmp = nums[n1];
nums[n1] = nums[n2];
nums[n2] = tmp;
}
}
<出力確認>
$ javac QuickSortTest.java
$ java QuickSortTest
9, 9, 1, 3, 9, 0, 6, 7, 4, 7,
0, 1, 3, 4, 6, 7, 7, 9, 9, 9,
2-2-3. VBA
<ソースコード>
'クイックソート
'引数(nums=対象となる配列、s=配列の開始位置、e=配列の終了位置)
Sub QuickSort(nums() As Long, s As Long, e As Long)
If s >= e Then Exit Sub '開始位置sが終了位置e以降になる場合は関数を抜ける
Dim i As Long
Dim p As Long: p = s
Call Swap(nums(s), nums((s + e) \ 2)) '配列中央の値を基準値にして先頭と入れ替え
For i = s + 1 To e
If nums(i) < nums(s) Then 'nums(s)を基準値として数値を比較していく
p = p + 1 '基準値より小さい数があるごとにpを1つ進める
Call Swap(nums(i), nums(p)) 'Swap関数で入れ替えを行う。
End If
Next
Call Swap(nums(s), nums(p)) 'Swap関数で入れ替え
Call QuickSort(nums, s, p - 1) '基準値より小さいグループを再帰処理
Call QuickSort(nums, p + 1, e) '基準値より大きいグループを再帰処理
End Sub
'スワップ
Sub Swap(a As Variant, b As Variant)
Dim tmp As Variant
tmp = a
a = b
b = tmp
End Sub
<出力確認>
Sub OutputQuickSort()
Dim nums() As Long
Call CreateArray(nums, 10) '配列を作成
Call PrintArray(nums) 'ソート前の配列を出力
Call QuickSort(nums, 0, UBound(nums)) 'クイックソートを実行
Call PrintArray(nums) 'ソート後の配列を出力
End Sub
※CreateArray関数
と、PrintArray関数
はヒープソートと同じものを使用しています。
1, 8, 5, 3, 1, 9, 0, 3, 0, 5,
0, 0, 1, 1, 3, 3, 5, 5, 8, 9,
2-2-4. Python
<ソースコード>
import random
# クイックソート
def quick_sort(nums, s ,e):
if s >= e: return
p, h = s, (s + e) // 2
nums[s], nums[h] = nums[h], nums[s]
for i in range(s + 1, e + 1):
if nums[i] < nums[s]:
p += 1
nums[p], nums[i] = nums[i], nums[p]
nums[s], nums[p] = nums[p], nums[s]
quick_sort(nums, s ,p - 1)
quick_sort(nums, p + 1 ,e)
# クイックソートの実行
n = 10
nums = [random.randint(0, n - 1) for i in range(n)]
print(nums) # ソート前の配列出力
quick_sort(nums, 0, n - 1) # クイックソート
print(nums) # ソート後の配列出力
<出力確認>
> python QuickSort.py
[9, 2, 8, 7, 2, 3, 5, 4, 0, 7]
[0, 2, 2, 3, 4, 5, 7, 7, 8, 9]
3. マージソート
マージソートは、元の配列の並び方に影響を受けることがあまりなく、処理速度もクイックソート並みに早いです。
マージを行う際に、追加の記憶領域が必要となってしまいますが(in-placeではない = not-in-place)、無駄の少ない綺麗なアルゴリズムだと思います(個人的に)。
考え方と実装方法は、おおよそ「基本情報技術者試験平成22年度春期午後問8」に基づいています。
3-1. マージソートのアルゴリズム概要
マージソートは、以下の図のように配列を最小単位まで分割した上で、昇順でマージを繰り返していくアルゴリズムです。
そして、マージ(並べ替え)をどうするかですが、昇順でマージを行う処理は次のような考え方で実装します。
<マージの実装方法>
実際にコードを書く場合は、次の図のように、半分(後半部分)は元の配列に残したまま、もう半分(前半部分)のみを取り出した上でマージ処理を行っていくのが効率的です。
これにより、追加で使用するメモリの領域が半分で済み、メモリのコピーも半分で済みます。
<前半部分と後半部分の値が同じ場合>
なお、前半部分と後半部分の先頭部分の要素が、それぞれ同じ値の場合は、前半部分を優先してマージします。
そうすることで、「同等なデータのソート前の順序が、ソート後も保存される」こととなります(これを「安定ソート」と言います)。
3-2. マージソートのサンプルコード
3-2-1. C言語
<ソースコード>
#include <stdio.h>
#include <stdlib.h> // malloc関数で使用
#include <time.h> // time関数、clock関数で使用
// マージソート
void merge_sort(int *nums, int s, int e) {
// 配列の分割位置を決める
int h = (s + e) / 2; // hは中央値
int lenl = h - s + 1; // lenlは前半部分の配列の要素数(わかりやすくするため変数に格納)
int lenr = e - h; // lenrは後半部分の配列の要素数(わかりやすくするため変数に格納)
// 分割した配列が2以上の要素を持つときは再帰処理を行う(再帰処理の終了後は各配列が昇順になっている)
if (lenl > 1) merge_sort(nums, s, h);
if (lenr > 1) merge_sort(nums, h + 1, e);
// 前半部分を新たな配列に格納
int *tmpnums = malloc(lenl * sizeof(int)); // 分割した配列を格納するメモリを確保(gccでは int tmpnums[lenl]; でもOK)
for (int i = 0; i < lenl; i++) tmpnums[i] = nums[s + i];
// 2つの配列を昇順にマージ
int nl = 0, nr = 0;
for (int i = s; i <= e; i++) {
if (nl > lenl - 1) break; // 前半部分の要素が全てマージされた場合は全ての並べ替えが終了
if (nr > lenr - 1 || tmpnums[nl] <= nums[h + 1 + nr]) {
nums[i] = tmpnums[nl++]; // 後半部分の要素が全てマージ or [前半部分の要素]<=[後半部分の要素] の場合
} else {
nums[i] = nums[h + 1 + nr++]; // [前半部分の要素]>[後半部分の要素] の場合
}
}
// メモリの解放
free(tmpnums);
}
// マージソートの実行
int main(void) {
// ソート用の配列を作成
srand((unsigned int)time(NULL)); // 乱数の発生をランダムにする
int n = 10;
int *nums = malloc(n * sizeof(int)); // int型配列のメモリを確保
for (int i = 0; i < n; i++) nums[i] = (int)rand() % n; // ランダムな値を代入
for (int i = 0; i < n; i++) printf("%d, ", nums[i]); // ソート前の配列出力
printf("\n");
merge_sort(nums, 0, n - 1); // マージソートの実行
for (int i = 0; i < n; i++) printf("%d, ", nums[i]); // ソート後の配列出力
printf("\n");
return 0;
}
可読性優先で冗長な書き方をしているため、コードが長く見えます。
変数を減らして整理するとmerge_sort
部分だけであれば10行くらいで済みます。
<出力確認>
$ gcc merge_sort.c
$ ./a.out
9, 4, 6, 9, 8, 5, 0, 5, 5, 3,
0, 3, 4, 5, 5, 5, 6, 8, 9, 9,
3-2-2. Java
<ソースコード>
import java.util.Random;
public class MergeSortTest {
public static void main(String[] args) {
// ソート用の配列を作成
int n = 10;
int nums[] = new int[n];
Random rand = new Random(); // 乱数のインスタンスを作成
for (int i = 0; i < n; i++) nums[i] = rand.nextInt(n); // ランダムな値を代入
for (int i = 0; i < nums.length; i++) System.out.print(nums[i] + ", "); // ソート前の配列出力
System.out.print("\n");
MergeSort(nums, 0, n - 1); // マージソートの実行
for (int i = 0; i < nums.length; i++) System.out.print(nums[i] + ", "); // ソート前の配列出力
System.out.print("\n");
}
public static void MergeSort(int nums[], int s, int e) {
// 配列の分割位置を決める
int h = (s + e) / 2; // hは中央値
int lenl = h - s + 1; // lenlは前半部分の配列の要素数(わかりやすくするため変数に格納)
int lenr = e - h; // lenrは後半部分の配列の要素数(わかりやすくするため変数に格納)
// 分割した配列が2以上の要素を持つときは再帰処理を行う(再帰処理の終了後は各配列が昇順になっている)
if (lenl > 1) MergeSort(nums, s, h);
if (lenr > 1) MergeSort(nums, h + 1, e);
// 前半部分を新たな配列に格納
int tmpnums[] = new int[lenl]; // 分割した配列を格納する配列
for (int i = 0; i < lenl; i++) tmpnums[i] = nums[s + i];
// 2つの配列を昇順にマージ
int nl = 0, nr = 0;
for (int i = s; i <= e; i++) {
if (nl > lenl - 1) break; // 前半部分の要素が全てマージされた場合は全ての並べ替えが終了
if (nr > lenr - 1 || tmpnums[nl] <= nums[h + 1 + nr]) {
nums[i] = tmpnums[nl++]; // 後半部分の要素が全てマージ or [前半部分の要素]<=[後半部分の要素] の場合
} else {
nums[i] = nums[h + 1 + nr++]; // [前半部分の要素]>[後半部分の要素] の場合
}
}
}
public static void Swap(int nums[], int n1, int n2) {
int tmp = nums[n1];
nums[n1] = nums[n2];
nums[n2] = tmp;
}
}
<出力確認>
$ javac MergeSortTest.java
$ java MergeSortTest
3, 1, 6, 2, 3, 0, 7, 9, 3, 1,
0, 1, 1, 2, 3, 3, 3, 6, 7, 9,
3-2-3. VBA
<ソースコード>
Sub MergeSort(nums() As Long, s As Long, e As Long)
Dim i As Long
Dim h As Long: h = (s + e) \ 2
Dim numsTmp() As Long: ReDim numsTmp(h - s)
If h - s > 0 Then Call MergeSort(nums, s, h)
If e - h - 1 > 0 Then Call MergeSort(nums, h + 1, e)
For i = 0 To h - s
numsTmp(i) = nums(s + i)
Next
Dim nl As Long: nl = 0
Dim nr As Long: nr = 0
For i = s To e
If nl > h - s Then Exit For
If nr > e - h - 1 Then
nums(i) = numsTmp(nl)
nl = nl + 1
ElseIf numsTmp(nl) < nums(h + 1 + nr) Then
nums(i) = numsTmp(nl)
nl = nl + 1
Else
nums(i) = nums(h + 1 + nr)
nr = nr + 1
End If
Next
End Sub
<出力確認>
Sub OutputMergeSort()
Dim nums() As Long
Call CreateArray(nums, 10) '配列を作成
Call PrintArray(nums) 'ソート前の配列を出力
Call MergeSort(nums, 0, UBound(nums))
Call PrintArray(nums) 'ソート後の配列を出力
End Sub
※CreateArray関数
と、PrintArray関数
はヒープソートと同じものを使用しています。
1, 3, 9, 6, 5, 7, 2, 0, 8, 5,
0, 1, 2, 3, 5, 5, 6, 7, 8, 9,
3-2-4. Python
<ソースコード>
import random
# マージソート
def merge_sort(nums, s ,e):
h = (s + e) // 2
lenl, lenr = h - s + 1, e - h
if lenl > 1: merge_sort(nums, s, h)
if lenr > 1: merge_sort(nums, h + 1, e)
tmp_nums = [nums[s + i] for i in range(lenl)]
nl = nr = 0
for i in range(s, e + 1):
if nl > lenl - 1: break
if nr > lenr - 1 or tmp_nums[nl] <= nums[h + 1 + nr]:
nums[i] = tmp_nums[nl]
nl += 1
else:
nums[i] = nums[h + 1 + nr]
nr += 1
# マージソートの実行
n = 10
nums = [random.randint(0, n - 1) for i in range(n)]
print(nums) # ソート前の配列出力
merge_sort(nums, 0, n - 1) # マージソート
print(nums) # ソート後の配列出力
<出力確認>
> python MergeSort.py
[7, 8, 8, 1, 1, 4, 8, 2, 9, 2]
[1, 1, 2, 2, 4, 7, 8, 8, 8, 9]
4. バブルソート
バブルソートは処理速度が遅いですが、アルゴリズムが単純なので、簡単に作成することができます。
データが大量でなければ、バブルソートで十分なことも多いです。
4-1. バブルソートのアルゴリズム概要
バブルソートは、以下の図のように隣り合う要素を順に比較して、値が大きいものを後ろに移動させていくアルゴリズムです。
一巡するたびに、一番大きい値が末尾に置かれて確定していきます。
バブル(泡)がどんどん上に上っていくように、大きい値が末尾に移動して確定していくというイメージです。
バブルソートのイメージ
バブルソートもIn-placeアルゴリズム(元の配列に要素を置いたまま交換により並べ替えをするアルゴリズム)となります。
4-2. バブルソートのサンプルコード
4-2-1. C言語
bubble_sort
関数自体は正味3行程度です。
<ソースコード>
#include <stdio.h>
#include <stdlib.h> // malloc関数で使用
#include <time.h> // time関数、clock関数で使用
void swap(int *n1, int *n2);
// バブルソート
void bubble_sort(int *nums, int numslen) {
for (int i = numslen - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) swap(&nums[j], &nums[j + 1]);
}
}
}
// スワップ(入れ替え)関数
void swap(int *n1, int *n2) {
int tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}
// バブルソートの実行
int main(void) {
// ソート用の配列を作成
srand((unsigned int)time(NULL)); // 乱数の発生をランダムにする
int n = 10;
int *nums = malloc(n * sizeof(int)); // int型配列のメモリを確保
for (int i = 0; i < n; i++) nums[i] = (int)rand() % n; // ランダムな値を代入
for (int i = 0; i < n; i++) printf("%d, ", nums[i]); // ソート前の配列出力
printf("\n");
bubble_sort(nums, n); // バブルソートの実行
for (int i = 0; i < n; i++) printf("%d, ", nums[i]); // ソート後の配列出力
printf("\n");
return 0;
}
<出力確認>
$ gcc bubble_sort.c
$ ./a.out
8, 5, 6, 3, 1, 0, 5, 2, 2, 1,
0, 1, 1, 2, 2, 3, 5, 5, 6, 8,
4-2-2. Java
<ソースコード>
import java.util.Random;
public class BubbleSortTest {
public static void main(String[] args) {
// ソート用の配列を作成
int n = 10;
int nums[] = new int[n];
Random rand = new Random(); // 乱数のインスタンスを作成
for (int i = 0; i < n; i++) nums[i] = rand.nextInt(n); // ランダムな値を代入
for (int i = 0; i < nums.length; i++) System.out.print(nums[i] + ", "); // ソート前の配列出力
System.out.print("\n");
BubbleSort(nums); // バブルソートの実行
for (int i = 0; i < nums.length; i++) System.out.print(nums[i] + ", "); // ソート前の配列出力
System.out.print("\n");
}
// バブルソート
public static void BubbleSort(int nums[]) {
for (int i = nums.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) Swap(nums, j, j + 1);
}
}
}
public static void Swap(int nums[], int n1, int n2) {
int tmp = nums[n1];
nums[n1] = nums[n2];
nums[n2] = tmp;
}
}
<出力確認>
$ javac BubbleSortTest.java
$ java BubbleSortTest
2, 5, 9, 9, 1, 9, 2, 4, 0, 1,
0, 1, 1, 2, 2, 4, 5, 9, 9, 9,
4-2-3. VBA
<ソースコード>
'バブルソート
Sub BubbleSort(nums() As Long)
Dim i As Long
Dim j As Long
For i = UBound(nums) - 1 To 0 Step -1 '比較する範囲を1つずつ小さくしていく
For j = 0 To i
If nums(j) > nums(j + 1) Then
Call Swap(nums(j), nums(j + 1)) '前方の値の方が大きければ数値を入れ替える
End If
Next
Next
End Sub
'スワップ関数(値aと値bを入替えるプローシージャ)
Sub Swap(a As Variant, b As Variant)
Dim tmp As Variant
tmp = a
a = b
b = tmp
End Sub
<出力確認>
'BubbleSortの出力
Sub OutputBubbleSort()
Dim nums() As Long
Call CreateArray(nums, 10) '配列を作成
Call PrintArray(nums) 'ソート前の配列を出力
Call BubbleSort(nums) 'バブルソートを実行
Call PrintArray(nums) 'ソート後の配列を出力
End Sub
※CreateArray関数
と、PrintArray関数
はヒープソートと同じものを使用しています。
7, 2, 0, 9, 8, 8, 7, 6, 4, 2,
0, 2, 2, 4, 6, 7, 7, 8, 8, 9,
4-2-4. Python
<ソースコード>
import random
# バブルソート
def bubble_sort(nums):
for i in reversed(range(len(nums))):
for j in range(i):
if nums[j] > nums[j + 1]: nums[j], nums[j + 1] = nums[j + 1], nums[j]
# バブルソートの実行
n = 10
nums = [random.randint(0, n - 1) for i in range(n)]
print(nums) # ソート前の配列出力
bubble_sort(nums) # バブルソート
print(nums) # ソート後の配列出力
<出力確認>
> python BubbleSort.py
[4, 3, 1, 4, 6, 8, 9, 6, 5, 0]
[0, 1, 3, 4, 4, 5, 6, 6, 8, 9]
5. 速度比較
最後に、各ソートアルゴリズムごと、各言語ごとに、処理速度の比較をしておきます。
実測結果は、教科書どおりにコンパイラ言語(C言語、Java)の方が速く、インタプリタ言語(VBA、Python)は10倍ほどの処理速度がかかるという結果になりました。
しかし、Pythonには奥の手(固有のSortメソッド)があり、コンパイラ言語並みのスピードを出すこともできます。
<実測結果概要>
要素数:100,000(配列の並びはランダム)
環境:Windows10(VBAがあるので、Windowsで比較しています。)
単位:秒(10回計測した平均値)
言語 | ヒープソート | クイックソート | マージソート | バブルソート | 固有メソッド |
---|---|---|---|---|---|
C言語 | 0.029 | 0.015 | 0.024 | 31.14 | - |
Java | 0.022 | 0.018 | 0.029 | 16.092 | 0.021 |
VBA | 0.904 | 0.244 | 0.161 | 528.979 | - |
Python | 1.204 | 0.252 | 0.487 | 710.887 | 0.017 |
ソートアルゴリズム別に見ると、クイックソートが一番速いです。
配列の並びに左右されず安定的なスピードが出るのは、マージソートとヒープソートになります。
5-1. 計算量
本記事で取り上げた4つのソートアルゴリズムの計算量は次のとおりとなります(詳しくはこちらを参照)。
ソート種別 | 平均計算量 | 最大計算量 | 安定ソート |
---|---|---|---|
ヒープソート | O(nlog n) | O(nlog n) | × |
クイックソート | O(nlog n) | O(n2) | × |
マージソート | O(nlog n) | O(nlog n) | ○ |
バブルソート | O(n2) | O(n2) | ○ |
バブルソートの計算量は、要素数nの2乗に比例するので、大きな配列に使用するのは無理が生じます。
クイックソートは、基準値の選定を誤るとバブルソート並みに時間が掛かるので要注意です。
5-2. 処理速度の計測結果
5-2-1. C言語
当然ですが、C言語は比較的処理速度が速いです。
ランダムな分布であれば、クイックソートが一番処理時間が短くて済みました。
<速度計測結果>
要素数:100,000(配列の並びはランダム)
環境:Windows10
単位:秒
試行 | ヒープソート | クイックソート | マージソート | バブルソート |
---|---|---|---|---|
1 | 0.028 | 0.016 | 0.022 | 31.157 |
2 | 0.027 | 0.015 | 0.024 | 31.458 |
3 | 0.029 | 0.015 | 0.024 | 31.537 |
4 | 0.029 | 0.016 | 0.024 | 30.812 |
5 | 0.03 | 0.015 | 0.023 | 30.975 |
6 | 0.028 | 0.015 | 0.024 | 31.111 |
7 | 0.028 | 0.015 | 0.024 | 31.236 |
8 | 0.028 | 0.015 | 0.023 | 30.99 |
9 | 0.029 | 0.015 | 0.024 | 31.219 |
10 | 0.029 | 0.015 | 0.025 | 30.903 |
平均 | 0.029 | 0.015 | 0.024 | 31.14 |
5-2-2. Java
Javaも処理速度がかなり速いです。
ヒープソートとバブルソートにおいては、C言語よりも短時間で処理が終わっています(なぜかは分かりません…)。
なお、Javaには、あらかじめソートメソッドがいくつか用意されています(詳しくは、Javaのソートの方法を一通り確認できるページを参照してください)。
ここでは、一般的と思われる、java.util.Arraysのsort()メソッドの処理速度も合わせて比較しておきます(次のソースコードを使用)。
import java.util.Random;
import java.math.BigDecimal;
public class JavaSortTest {
public static void main(String[] args) {
int n = 100000;
int nums[] = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) nums[i] = rand.nextInt(n);
long start = System.nanoTime(); // スタート時間を記録
java.util.Arrays.sort(nums); // ソートの実行
double processing_time = (System.nanoTime() - start) / Math.pow(10, 9);
System.out.println(BigDecimal.valueOf(processing_time).toPlainString()); // 処理時間を出力
}
}
<速度計測結果>
要素数:100,000(配列の並びはランダム)
環境:Windows10
単位:秒
試行 | ヒープソート | クイックソート | マージソート | バブルソート | sort()メソッド |
---|---|---|---|---|---|
1 | 0.023 | 0.015 | 0.031 | 16.199 | 0.013 |
2 | 0.023 | 0.014 | 0.03 | 16.125 | 0.013 |
3 | 0.024 | 0.021 | 0.027 | 16.15 | 0.029 |
4 | 0.021 | 0.017 | 0.03 | 16.058 | 0.037 |
5 | 0.019 | 0.022 | 0.031 | 15.88 | 0.037 |
6 | 0.021 | 0.016 | 0.03 | 16.174 | 0.013 |
7 | 0.021 | 0.016 | 0.027 | 16.329 | 0.021 |
8 | 0.02 | 0.028 | 0.027 | 15.894 | 0.013 |
9 | 0.021 | 0.016 | 0.027 | 16.084 | 0.016 |
10 | 0.023 | 0.015 | 0.028 | 16.028 | 0.014 |
平均 | 0.022 | 0.018 | 0.029 | 16.092 | 0.021 |
5-2-3. VBA
VBAだと、CやJavaと比べると10倍くらいの時間が掛かっているようです。
特徴は、マージソートの方がクイックソートより速いことです。他の言語と異なる理由は分かりません。
バブルソートは、10万要素だと10分近く掛かるので、もうほとんどまともに動きません。
100万要素だと、単純に15時間ぐらいくらい掛かることになります。
<速度計測結果>
要素数:100,000(配列の並びはランダム)
環境:Windows10
単位:秒
試行 | ヒープソート | クイックソート | マージソート | バブルソート |
---|---|---|---|---|
1 | 0.875 | 0.23 | 0.188 | 520.281 |
2 | 0.922 | 0.227 | 0.188 | 590.551 |
3 | 0.953 | 0.266 | 0.156 | 587.059 |
4 | 0.895 | 0.266 | 0.172 | 545.402 |
5 | 0.887 | 0.234 | 0.156 | 503.906 |
6 | 0.891 | 0.219 | 0.125 | 538.902 |
7 | 0.875 | 0.266 | 0.156 | 497.254 |
8 | 0.859 | 0.219 | 0.141 | 514.914 |
9 | 1 | 0.234 | 0.156 | 499.352 |
10 | 0.887 | 0.281 | 0.172 | 492.168 |
平均 | 0.904 | 0.244 | 0.161 | 528.979 |
5-2-4. Python
Pythonは、私の拙いコードの書き方が原因かもしれませんが、VBA並みもしくはそれ以上の処理時間が掛かっています。
ただし、Pythonには次のようなsortメソッドが用意されています。
これも同条件で速度を計測しましたが、C言語やJava並みの速度が出ています。この辺もPythonの良いところですね。
import random
import time # timeモジュールをインポート
# ソートの実行
n = 100000
nums = [random.randint(0, n - 1) for i in range(n)]
start = time.time() # スタート時間を記録
nums.sort() # ソート
processing_time = time.time() - start
print(processing_time) # 処理時間を出力
<速度計測結果>
要素数:100,000(配列の並びはランダム)
環境:Windows10
単位:秒
試行 | ヒープソート | クイックソート | マージソート | バブルソート | Sortメソッド |
---|---|---|---|---|---|
1 | 1.001 | 0.218 | 0.5 | 710.887 | 0.015 |
2 | 1.011 | 0.227 | 0.493 | - | 0.016 |
3 | 1.284 | 0.37 | 0.476 | - | 0.017 |
4 | 1.352 | 0.237 | 0.484 | - | 0.018 |
5 | 1.043 | 0.232 | 0.476 | - | 0.019 |
6 | 1.018 | 0.236 | 0.48 | - | 0.016 |
7 | 1.523 | 0.23 | 0.484 | - | 0.017 |
8 | 1.367 | 0.312 | 0.493 | - | 0.017 |
9 | 1.049 | 0.215 | 0.506 | - | 0.017 |
10 | 1.386 | 0.235 | 0.482 | - | 0.017 |
平均 | 1.204 | 0.252 | 0.487 | 710.887 | 0.017 |
※バブルソートは、とんでもなく遅いので、1回だけしか実行していません。
5-3. 【参考】処理時間計測のソースコード
参考までに、処理時間を計測したソースコードも残しておきます。
ソートアルゴリズムのコードは省略しています。
5-3-1. Python
#include <stdio.h>
#include <stdlib.h> // malloc関数で使用
#include <time.h> // time関数、clock関数で使用
void quick_sort(int *nums, int s, int e);
// 中略
// クイックソートの実行
int main(void) {
srand((unsigned int)time(NULL));
int n = 100000;
int *nums = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) nums[i] = (int)rand() % n;
int start = clock(); // スタート時間を記録
quick_sort(nums, 0, n - 1); // クイックソートの実行
int end = clock();
double processing_time = (double)(end - start) / CLOCKS_PER_SEC;
printf("%f\n", processing_time); // 処理時間を出力
return 0;
}
5-3-2. Java
import java.util.Random;
import java.math.BigDecimal;
public class QuickSortTest {
public static void main(String[] args) {
int n = 100000;
int nums[] = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) nums[i] = rand.nextInt(n);
long start = System.nanoTime(); // スタート時間を記録
QuickSort(nums, 0, n - 1); // クイックソートの実行
double processing_time = (System.nanoTime() - start) / Math.pow(10, 9);
System.out.println(BigDecimal.valueOf(processing_time).toPlainString()); // 処理時間を出力
}
public static void QuickSort(int nums[], int s, int e) {
// 中略
}
}
5-3-3. VBA
Sub SortSpeed()
Dim n As Long: n = 100000
Dim nums() As Long
Call CreateArray(nums, n) '配列を作成
Dim startTime As Double: startTime = Timer 'スタート時間を記録
Call QuickSort(nums, 0, UBound(nums)) 'クイックソート
Dim processingTime As Double: processingTime = Timer - startTime
Debug.Print processingTime
End Sub
5-3-4. Python
import random
import time # timeモジュールをインポート
# クイックソート
def quick_sort(nums, s ,e):
# 中略
# クイックソートの実行
n = 100000
nums = [random.randint(0, n - 1) for i in range(n)]
start = time.time() # スタート時間を記録
quick_sort(nums, 0, n - 1) # クイックソート
processing_time = time.time() - start
print(processing_time) # 処理時間を出力
さいごに
図表に時間を取られて途中で先が見えなくなりましたが、何とか最後まで書けたので、まあ良しとします。
Pythonは使いこなせると便利だろうと思いますので、もう少し学習を進めていきたいところです。