配列 -ソート-

ホームC#プログラミング応用講義 > ソート

目次

Array.Sort()

配列を利用する最大のメリットはソートを簡単に行える ことです。ソートとは何らかの決まりに従った順番に並び替える ことを意味します。

配列をソートするのは非常に簡単です。なぜなら Array クラスSort() メソッドが用意され、これを呼び出すことで自動的にソートすることができるからです。
ここでは適当な整数値で配列を初期化しておき、それをソートするプログラムを作ってみます。
using System;

class Sample
{
public static void Main(string[] args)
{
int[] x = new int[] {26,54,78,63,45,21,34,10,23,85};
Array.Sort(x);
for (int i=0;i<x.Length;i++)
Console.WriteLine(x[i]);
}
}
配列 x を初期化していますが、これを見ただけで小さいほうから大きいほうへ一瞬で並べることができればあなたの頭はパソコンなみですが、そう簡単にはできませ ん。
ここでは単に
Array.Sort(配列名);
を利用して並び替えています。これは static なメンバであるため、オブジェクトを生成する必要はありません。

バブルソート

Array.Sort() で簡単にソートできることはわかりましたが、ただこれだけをやってもプログラマとしては面白くないかもしれません。
そこで今回はあるソートアルゴリズムを紹介します。

ソートアルゴリズムは大変多く存在しますが、その中で最も簡単そうなのが「バブルソート」です。
バブル = 泡は水中で↑方向に移動します。バブルソートでは大きいものと小さいものをまるでバブルのように片一方に寄せることでソートを実現します。
using System;

class Sample
{
public static void Main(string[] args)
{
int[] x = {26,54,78,63,45,21,34,10,23,85};
int a,b,t;
int length = x.Length;
// -----バブルソート.コア----

// 配列の要素数だけ繰り返す
for (a=0;a<length;a++){
/* 要素数-1で初期化
この初期化の値が最大になり、
徐々に減っていきます
*/
for (b=length-1;b>=a;b--){
/* インデックスが小さいのに
入っている値が大きい場合は
それをひっくり返す
*/
if (x[b-1]>x[b]){
t = x[b-1];
x[b-1] = x[b];
x[b] = t;
}
}
}
// ------ここまで-----
for (int i=0;i<length;i++)
Console.WriteLine(x[i]);
}
}
バブルソートはインデックスの順序とその内容の数の大小が逆の場合にひっくり返していくことで、ぶくぶくと上がっていく泡の ように大きい数は右へ、小さい数は左へと移動していきます。ここにおける右はインデックスの大きいもので、左が小さいものです。

A と B の値をひっくり返すには t という別枠を用意しておくことで実装できます。t はバックアップ用の変数です。
まず、B の値をバックアップするために t に入れておきます。(t = B)
次に B が空きますから B に A の値を入れます。(B = A) この時点で A のデータは B に移されるので不要となりますが、まだ保持しています。
最後に始めにバックアップとしてとっておいた t の値を A に入れます。(A = t) t には始めの B が入っていましたから結局、
A ← t ← B
|            |
→------↑

と、ぐるっと回って A と B が入れかわります。これでインデックスの順序通りに大小になっていきます。

また、繰り返される回数は 要素数-1 になります。繰り返し自体は、2つ目のものが「デ クリメント」であることに注意してください。
それぞれのステートメントは非常に単純です。

バブルソートは要素数が大きくなると繰り返しの回数も多くなるので能率がいいとはいえません。それでも上のサンプルのように10個程度なら一瞬でできま す。

Array.Sort() がどのようなアルゴリズムを利用しているのかは知りませんが、ソートアルゴリズムは大変複雑になるものも多数あります。
このバブルソートは実際にソートするのが先ほど説明した if のひっくり返す部分で、あとは繰り返すだけなのであまり複雑ではありません。

現実的にソートを利用する場合は Array.Sort() でほとんど事足りますが、ソートアルゴリズムも1つくらいは知っておいたほうがいいでしょう。

[ ステップアップC# ] [ C#プログラミング応用講義 ]