HN 日本語サマリー

← 一覧へ戻る
プログラミング

信じられない、ソートできるなんて

I Can't Believe It Can Sort (yugen-tsuki.github.io)

31 pointsby Muhammad52336 コメント

要約

この記事では、「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 + " ");
    }
                                
}