algorithm - 最速のソート手法

Question

過去数日間、さまざまな並べ替えアルゴリズムを試してきました。1) O(n^2) 時間の複雑さのソートを使用するアルゴリズム 2) O(n log n) の時間の複雑さ、インプレースおよびアウトオブプレースのソート手法

線形時間以下でソートするソートアルゴリズムがあるかどうか疑問に思っています。最良の場合、スペースの複雑さを伴う線形時間ソートに近い基数ソートについて聞いたことがあります。誰かが私を啓発できますか？

Answer 1

最速の一般的なソートはマージソートです。これは、マップ/リデュースパターンを利用できます（クイックソートではできません）。

ただし、データについて何か知っている場合は、データセットをそれよりも高速に並べ替えることができる場合があります。

意味のないO（n）より速くソートすることはできません。少なくとも各要素を1回処理する必要があります。

あなたの言及した基数ソートに応じて：

（ウィキペディアから）

基数ソートの効率は、k桁以下のn個のキーに対してO（k・n）です。kは定数として表されることがあります。これにより、基数ソートは、すべてO（n・log（n））である最良の比較ベースのソートアルゴリズムよりも優れたものになります（nが十分に大きい場合）。ただし、一般にkは定数とは見なされません。特に、すべてのキーが異なるという一般的な（ただし暗黙的な）仮定の下では、kは少なくともlog（n）のオーダーでなければならず、他の種類よりも良い結果は得られません。

Answer 2

リストがソートされているかどうかを判断するには、すべての N 個の要素を調べる必要があるため、O(N) 未満でソートすることはできません。つまり、O(N) です。リスト内の他の要素と比較してソートする場合、O(NlogN) よりも高速にソートすることはできませんが、データについて何か知っている場合はソートできます。たとえば、データが英語の文字列であることがわかっている場合、並べ替える前にそれらをバケットに入れることができる場合があります。たとえば、A で始まるすべての文字列を 1 つのバケットに入れ、B を別のバケットに入れます。これは速いでしょう。ただし、すべてのバケットに同じ数の文字列が含まれるわけではないため、各バケットをかなり大きくする必要がある場合があります。おそらく、1000 個の文字列を収めるのに十分な大きさです。

次に、個々のバケットを並べ替えます。これは高速です。

データの均一な分布 (つまり、各文字で始まる 400 個の文字列、もちろんありません) の場合、これは O(N) + O(Nlog N/M) になると推定します。ここで、M は数値です。バケツの。

もちろん、2 番目の文字のバケットをネストすることもできますが、バケットが多ければ多いほど、必要なスペースが大きくなります。その場でバケットを拡張する必要があると実行時間がかかるため、最初から十分な大きさにする必要があります。これは、データの分布についてすべてを知っているわけではないため、それらの多くが必要以上に大きくなることを意味します。

ライブラリの並べ替えも検討する価値があるかもしれません。

Answer 3

線形時間で実行されるソート アルゴリズムには、カウント ソート、基数ソート、バケット ソートなどがあります。これらのアルゴリズムの落とし穴は、入力に関する仮定が必要なことです。カウントソートと基数ソートは、入力が狭い範囲の整数で構成されていることを前提としています。バケット ソートは、要素を一定間隔で均一に分散するランダム プロセスによって入力が生成されることを前提としています。Page3-6は、上記のアルゴリズムの概要を示しています。

Answer 4

(Edit to my previous bad post, sorry everybody)

One way to improve performance of sorting algorithms is parallel processing:

Parallel Sort Algorithm

In this post, performance of sequential and parallel QuickSort algorithm is compared using a list of integers. Performance is enhanced significantly in a dual core machine. QuickSort can even perform at O(log n) on a system with n processors, according to this article:

http://en.wikipedia.org/wiki/Merge_sort#Parallel_processing

It might sound unreal to have that many cores available, but with infrastructure as a service (Amazon Cloud, Azure...) it can be an available option for mission critical implementations.