3 種類のソーティングアルゴリズムの擬似コード (Cormen他、「Introduction to Algorithms (Second Edition)」より抜粋)。
SELECTION-SORT(A)
1 for j ← 1 to length[A]-1
2 do min ← j
3 for i ← j+1 to length[A]
4 do if A[i] < A[min]
5 then min ← i
6 exchange A[j] ←→ A[min]INSERTION-SORT(A)
1 for j ← 2 to length[A]
2 do key ← A[j]
3 # A[j] をソート済み順列 A[1 .. j-1] に挿入
4 i ← j-1
5 while i > 0 and A[i] > key
6 do A[i+1] ← A[i]
7 i ← i-1
8 A[i+1] ← key QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r)
3 QUICKSORT(A, p, q-1)
4 QUICKSORT(A, q+1, r)
PARTITION(A, p, r)
1 x ← A[r]
2 i ← p-1
3 for j ← p to r-1
4 do if A[j] <= x
5 then i ← i+1
6 exchange A[i] ←→ A[j]
7 exchange A[i+1] ←→ A[r]
8 return i+1一言で「プログラミング」と言っても、 アルゴリズムやデータ構造、 コンピュータアーキテクチャ、 プログラミング言語、 ソフトウェアのテスト技法、 開発ツールなどさまざまな知識や技術が求められる。
従って、一言で「プログラミングが苦手」と言っても、
- アルゴリズムやデータ構造が苦手である
- アルゴリズムやデータ構造をプログラムに変換するのが苦手である
- アルゴリズムやデータ構造をコンピュータのアーキテクチャに落とし込むのが苦手である
- 実装に用いる言語 (C 言語、Python 言語等) が苦手である
- プログラムのテストが苦手である
- プログラムのデバッグが苦手である
- 開発ツール (エディタ、コンパイラ、デバッガ、シェル) 等が苦手であるなどのさまざまな「苦手」がある。 多くの場合、 これらの知識・技術のうちの複数の「苦手」が重なって、 「プログラミングが苦手」となっている。
逆に言えば、プログラミングを得意にするためには、 それぞれの知識・技術を順番に習得してゆけばよい。 いわゆる「分割統治法」である。
プログラミングが苦手な人が、 例えば課題のプログラムを作成する、 最も簡単な方法は生成系 AI を使うというものである。
上記のような知識や技術がなくても、 AI にプロンプトとして与える「課題」が正確で厳密であれば (そしてそれほど複雑な課題でなければ)、 AI が正しいプログラムを書いてくれるであろう。
ただしこの場合、 生成系 AI を利用するスキルは向上するが、 上記のプログラミングに必要な知識・技術はまったく向上しないことに注意が必要である。 数学が苦手な人が、 自分で問題を解かず、 自分では作図せず、 自分では計算せずに、 ひたすら問題の「解答」を探して読んでいても数学力が向上しないのと同じである。
生成系 AI は非常に便利であるが、 「何のために使っているのか」、 「この使い方が自分の能力が向上するか」を常に考えるようにしよう。
プログラミングが苦手な人ほど、 複数のことを同時にやろうとして、 結局何をやっているのかわからなくなってしまう。
例えば、課題のプログラムを作成する時に、
- アルゴリズムをどうするか
- データ構造をどうするか
- アルゴリズムやデータ構造をどのようにプログラムに変換するか
- アルゴリズムやデータ構造をコンピュータのアーキテクチャにどう対応させるか
- 実装に用いる言語 (C 言語、Python 言語等) でどう書くか
- プログラムをどうやってテストするか
- プログラムのデバッグがどうやってするか
- 開発ツール (エディタ、コンパイラ) は知っている (素朴な) ものだけ使うとなっていて、 今何をしているのかわからなくなってしまう。 このように、 あまりよく考えずにとりあえず力づくで何とかしようとするアプローチを、 ブルートフォース (brute force) と言う。
ブルートフォースは、 精神的にもっとも楽だが、 最も効率が悪い手法であることが知られている。 ほとんど何も考えずに、 「とにかくやってみる」という手法なので、 論理的に、 計画的に、 戦略的に考える必要がまったくない。 まさに無計画に行きあたりばったりで取り組むので、 精神的な負担が最小である。 「何も考えなくても、 とにかく始められる」ので、 ブルートフォースで始めて、 いつまでも (延々と) ブルートフォースを続けてそこから離れられない人が大多数である。 ブルートフォースは精神的に楽であるから、 当然、 最も効率が悪い手法である。
私はプログラミングは大好きだし、 得意でもある。 しかし、 仮に私が上記のようなブルートフォースのアプローチを取ったなら、 まず間違いなくプログラムは完成しないだろう。
私がプログラミングが好きで得意なのは、 上記のような「ブルートフォースで全部一緒にまとめて考える」ということをしないからである。
ここでも重要なのは、いわゆるコンピュータサイエンスにおける「分割統治法」である。
---- 電子情報通信ハンドブック: 分割統治法 [divide and conquer]
分割統治法 [divide and conquer]
分割統治法は効率的なアルゴリズム設計法の代表格であり, 広く用いられている．与えられた問題をまず
いくつかのより小さい複数の部分問題に分割して, 次にそれらの部分問題に再帰的に手法を適用して解を求
め, そして最後にそれらの解を併合して最初の問題の解を得る手法である．ソーティング(マージソート,
クイックソート), 高速フーリエ変換, 行列積の計算などの基本的な問題に対してだけでなく, 計算幾何,
並列アルゴリズムなどでもしばしば用いられている．再帰法に基づくので計算時間は漸化式で表現され解析
されている．
(浅野)選択ソートを C 言語で、ブルートフォースで (途中まで) 実装してみよう。
まず、「選択ソート」とは以下のようなアルゴリズムである。
選択ソート (Selection Sort) は、配列の中から毎回最小値 (または最大値) を線形探
索で選び出し、それを未整列領域の先頭要素と交換する操作を繰り返すことで整列を行
う単純な比較ソートである。未整列部分を走査して最小値を選択する処理が常に O(n)
かかり、これを n 回繰り返すため計算量は入力分布に依らず **O(n²)** となる点が
特徴で、メモリ使用量が少なく動作も安定しているが、性能面では他の効率的なソート
(Merge Sort や Quick Sort) に劣る。 [ChatGPT 5.1]これを見て、 「ふむふむ」と言いながらおもむろにエディタに向かう。 「標準入力から配列の大きさを、 配列のデータを読み込んで、 それをソートして、 ソートが終わったら標準出力に書き出すか……」みたいなことをぼんやり考えながら、 以下のようなコードを書き始める。
#include <stdio.h>
#define MAXSIZE 1000
int main(void) {
int A[MAXSIZE];
int n;
if (scanf("%d", &n) == EOF)
return;
for (int i = 0; i < n; i++) {
if (scanf("%d", &A[i]) == EOF)
return;
}
}まさに「力づくの方法」である。 選択ソートくらい単純なプログラムなら、 ブルートフォースで何とかなるかもしれない。
しかし、 みなさんのプログラミングに関する技術はほとんど向上しない。 ブルートフォースでうまく行った (プログラムが完成できた) なら、 それは自身のスキルが上がったからではなく、 単に運が良かっただけである。
ブルートフォースのように、運に頼るアプローチを取ってはいけない。
分割統治法で、複雑な問題を分割して解く例を示そう。
さきほど、プログラムを書く時に考える必要がある以下のような項目を示した。
- アルゴリズムをどうするか
- データ構造をどうするか
- アルゴリズムやデータ構造をどのようにプログラムに変換するか
- アルゴリズムやデータ構造をコンピュータのアーキテクチャにどう対応させるか
- 実装に用いる言語 (C 言語、Python 言語等) でどう書くか
- プログラムをどうやってテストするか
- プログラムのデバッグがどうやってするか
- 開発ツール (エディタ、コンパイラ) は知っている (素朴な) ものだけ使う分割統治法では、 大きな問題を小さく分割して解く。 特に、 分割した問題が、 自明に解ける大きさになるまで小さく分割して解く、 というのがポイントである。
選択ソートを実装する、という例なら、例えば、
- 実装に用いる言語 (C 言語、Python 言語等) でどう書くかだけに集中することができる。
実際の例を示そう。
C 言語で書くよりも、 Python 言語等の表現力の高い言語で書いたほうがはるかに簡単であるから、 ここでは選択ソートを Python 言語で実装してみよう。
選択ソートの擬似コード (の一つ) は以下の通りである。
SELECTION-SORT(A)
1 for j ← 1 to length[A]-1
2 do min ← j
3 for i ← j+1 to length[A]
4 do if A[i] < A[min]
5 then min ← i
6 exchange A[j] ←→ A[min]そこで、「この擬似コードを、どうやったら Python で書けるか」だけに集中する。
上記の擬似コードを Python で書いた例が以下である。
def selection_sort(A):
for j in range(0, len(A) - 1):
min_ = j
for i in range(j + 1, len(A)):
if A[i] < A[min_]:
min_ = i
A[j], A[min_] = A[min_], A[j]ほぼ擬似コードのままだが、
- Python で for ループをどう書けばいいのか
- Python で配列の大きさをどう取得すればいいのか
- Pytyonn で min は組み込み関数である (だから名前の衝突を避けるべき)
- Python ではタプルの代入で値を交換できるという知識を使っている。
「これなら私にもできそう」と思わないだろうか? プログラミングが得意な人は、 ブルートフォースではなく、 こういう分割統治法のアプローチを取っているので、 それほど苦労せずにスイスイとプログラムが書けるのである。
最後に、選択ソートを C 言語で実装する例を示そう。
Python 言語より C 言語のほうが言語の表現力が低いので、もう少しだけ面倒である。
void selection_sort(int length, int *A)
{
for (int j = 0; j <= length - 2; j++) {
int min = j;
for (int i = j + 1; i <= length - 1; i++) {
if (A[i] < A[min])
min = i;
}
int tmp;
tmp = A[j]; A[j] = A[min]; A[min] = tmp;
}
}