信じられない、ソートできるなんて
I Can't Believe It Can Sort (yugen-tsuki.github.io)
要約
この記事では、「I Can't Believe It Can Sort」と呼ばれる、非常にシンプルながら非効率なソートアルゴリズムを紹介しています。このアルゴリズムは、二重ループを使って配列の要素を繰り返し比較・交換することでソートを行いますが、その計算量はO(n^2)であり、一般的なソートアルゴリズムと比較して効率は劣ります。論文からの引用とJavaでの実装例も示されています。
全文翻訳
信じられない、ソートできるなんて!
「I Can't Believe It Can Sort」アルゴリズムは、非常にシンプルですが非効率なソートアルゴリズムです。その名前の由来は、擬似コードを見ただけでは実際にソートできるとは思えないのに、それができてしまうからです。以下にその擬似コードを示します。
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]
この擬似コードは、Stanley P. Y. Fungによる論文「Is this the simplest (and most surprising) sorting algorithm ever?」からそのまま引用したものです。論文はこちらで見つけることができます。
擬似コードが示すように、「I Can't Believe It Can Sort」は、ネストされたループを使用して要素を繰り返し比較・交換することで配列がソートされるまで実行される、シンプルで非効率なソートアルゴリズムです。このアルゴリズムの時間計算量はO(n^2)であり、平均および最悪ケースのパフォーマンスがより優れたクイックソートやマージソートのような、よく知られたソートアルゴリズムよりもはるかに効率が悪いです。
以下にこのアルゴリズムのJava実装を示します。
import java.util.*;
import java.lang.*;
class ICantBelieveItCanSort{
public static void iCantBelieveItCanSort(int[] arr){
int n = arr.length;
for(int i=0; i<n; i++){
for(int j=0;j <n;j++){
if(arr[i]<arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String[] args){
int[] arr = {1,3,5,3,67,7,2,8,9,34,54,22,65,21};
iCantBelieveItCanSort(arr);
for(int i : arr)
System.out.print(i + " ");
}
}