Javaを利用したソートアルゴリズムについて今回は書いてみます。
備忘録として残す程度にします。
まず、バブルソート。
一般的に使われる頻度が高そうなアルゴリズム。大小を比較して順番を入れ替えていくものです。
bubble_Sort
static void bubble_Sort(int []data)
{
for(int s = data.length - 1; s > 0; --s)
{
for(int t = 0; t < s; ++t)
{
if(data[t] > data[t + 1])
{
int temp = data[t];
data[t] = data[t + 1];
data[t + 1] = temp;
}
}
}
}
次にクイックソート。
データの集合を基準値より大きいものと小さいものに振り分け、また振り分けたグループから新しい基準値を利用して同様の事を再帰的に繰り返すアルゴリズムです。
並び替えのアルゴリズムではもっとも早く終わります。
quick_Sort
static void quick_Sort(int []data, int left, int right){
if (left >= right) {
return;
}
int p = data[(left + right)/2];
int l = left;
int r = right;
int temp;
while(l <= r) {
while(data[l] < p) { ++l; }
while(data[r] > p) { --r; }
if (l <= r) {
temp = data[l];
data[l] = data[r];
data[r] = temp;
++l;
--r;
}
}
quick_Sort(data, left, r); // ピボットより左側をクイックソート
quick_Sort(data, l, right); // ピボットより右側をクイックソート
}
ちなみにバブルソートが15秒弱でクイックソートが0.2秒とかそこら辺でした。
クイックソート早い・・・。
[追記]
コメントでご指摘をいただき、修正しました。
修正後確認したらバブルソートは40秒でした。
これでバブルソートクイックソート共に正常に動きます。
ご迷惑をお掛けしました