分布数え上げソート : アルゴリズム
分布数え上げソートはキーの重複に対応しているといいました。キーが重複しているのは 3 です。整列後のふたつの 3 の位置(配列のインデックス)は 「Y - X」 と 「Y - 1」 で計算できます。この例だと「3 - 2 = 1」と「3 - 1 = 2」になります。 実際のプログラミングでは重複したキーの位置の計算は、作業用配列Bにコピーする時に(手順4で)配列Aの後ろから前へコピーしていくことで簡単に実装できます。 図解 特徴 バケットソートと同じくソート対象のデータがとりうる値の範囲をあらかじめわかっていなければなりません。作業領域もキーの個数を数えるための領域と結果を格納する領域が必要になります。あまりに大きな範囲のデータを取り扱うには RAM などに限度があるので物理的に不可能になります。しかし大きな作業領域と引き換えにデータの大小を比較しなくてよいので高速な整列処理を実現できます
ストゥージソート - Wikipedia
ストゥージソート（英: Stooge sort）は、再帰を用いたソートアルゴリズムのひとつである。 計算時間はO(nlog 3 / log 1.5 ) = O(n2.7095...)であり、これはマージソートなどの効率的なアルゴリズムよりも、それどころか非常に効率の悪い単純なソートの例としてよく挙げられるバブルソートよりも遅い。 アルゴリズムは以下の通りである。 もし末尾の値が先頭の値より小さければ、それらを入れ替える。 現在処理している部分列の要素数が3以上であれば、 リストの先頭2/3[1]に対してストゥージソートを行う。 リストの末尾2/3[1]に対してストゥージソートを行う。 リストの先頭2/3[1]に対して再びストゥージソートを行う。 そうでなければ終了。 実装[編集] algorithm stoogesort(array L, i = 0, j = length(L)-1) i
基数ソート
public void sort(int[] a){ // バケツに入っているデータ数を覚えるための配列です int[] bn=new int[bucket.length]; // 最下位桁の数字を見て、対応するバケツにデータを入れます。 for(int i=0;i<a.length;i++){ bucket[a[i]%m].add(new Integer(a[i])); notifier.notify(i,-1); } // 最初のバケツから順番にデータを取りだし、データの指定桁の値を見て、 // 対応するバケツにデータを追加します。 for(int j=1;j<k;j++){ // 現在、それぞれのバケツに何個のデータが入っているかを // 覚えておきます。 for(int b=0;b<bucket.length;b++) bn[b]=bucket[b].num; // 各バケツの先頭
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
基数ソート - Wikipedia
基数ソート（きすうソート、英: radix sort）は、「比較によらないソート」[1]のアルゴリズムの一つで、位取り記数法で表現可能な対象について、下の桁から順番にソートしてゆき、最後に最上位桁でソートすると、全体が順序通りに並ぶ、という手法である。 nをデータの数、kを桁数として、計算量のオーダーはO(nk)である。また、アルゴリズム自身の性質により、素直な実装が安定ソートになる。[2] 前提条件[編集] このアルゴリズムは、データの種類が有限で、最大値・最小値がはっきりしているという仮定を置いており、全ての入力データが「3桁の整数」や「2文字のアルファベット」など決まった形式であることが分かっていなければならない。なおそれに加え、ある値のデータが必ず一つしか現れないとか、同じ値のデータは同一のものとしてしまって良い、といった場合には、もはやソートするのではなく、単純に、全体が入る大き
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
