ソートの速度比較2(sort comparison)
forked from ソートの速度比較(sort comparison) (diff: 67)
高速ソート8種+2
ActionScript3 source code
/**
* Copyright shohei909 ( http://wonderfl.net/user/shohei909 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/jwKM
*/
package {
import flash.events.MouseEvent;
import flash.text.TextField;
import flash.display.Sprite;
import flash.utils.getTimer;
public class FlashTest extends Sprite{
private const LOOP:int = 1;
private const LENGTH:int = 50000;
private var t:TextField;
public function FlashTest() {
addChild( ( t= new TextField() ) ).width = t.height = 1000;
addEventListener( MouseEvent.CLICK, onClick );
ex();
}
private function onClick( e:MouseEvent ):void
{
ex();
}
private function ex():void
{
var i:int = 0;
var time1:int;
var time2:int;
var recode:Array = [];
var count:int = 0;
var arr:Array = ArrayUtil.random(LENGTH, LENGTH);
var a:Array;
var f:Function = function _(a:Number, b:Number ):Boolean { return a <= b; }
t.text = "要素数"+ LENGTH + "の配列をソート\n\n";
a = ArrayUtil.copy(arr);
time1 = getTimer();
a.sort( Array.NUMERIC );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Array.sort( Array.NUMERIC )", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
a.sort( function _(a:Number, b:Number):int{ return (a == b) ? 0 : (a < b) ? -1 : 1; } );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Array.sort( function () )", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.combSort( a, f );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Comb Sort", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.shellSort( a, f );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Shell Sort", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.quickSort( a, f );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Quick Sort", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.quickSort2( a, f );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Quick Sort2", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.margeSort( a, f );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Marge Sort", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.heapSort( a, f );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Heap Sort", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.easySmoothSort( a, f );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Easy Smooth Sort", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.shellectionSort( a, f );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Shellection Sort", time2 );
a = ArrayUtil.copy(arr);
time1 = getTimer();
ArrayUtil.uintRadixSort( a, LENGTH );
time2 = getTimer() - time1;
recode[count++] = new TimeData( "Radix Sort(unit only)", time2, "["+a+"]" );
/* templete
time1 = getTimer();
for( i = 0; i<LOOP; i++ )
{
}
time2 = getTimer() - time1;
recode[count++] = new TimeData( "", time2, "" );
*/
if( recode.length )
{
listup( recode );
}
t.appendText("clickで再計算");
}
private function listup( recode:Array ):void
{
var str:String = "";
recode.sortOn( "time", Array.NUMERIC );
var max:int = (recode[ recode.length - 1 ] as TimeData).time;
for( var i:int = 0, len:int = recode.length; i<len; i++)
{
var data:TimeData = recode[i] as TimeData;
var n:int = max / data.time * 100;
str += data.title + " :: " + data.time + " ms\t\t最低速に比べて約 " + n + " %高速";
if(data.ms == "") str += "\n";
else str += "\t\t" + data.ms + "\n";
}
t.appendText( str );
}
}
}
class TimeData{
public var title:String;
public var time:int;
public var ms:String; // なんか、おまけ要素
public function TimeData( title:String = "", time:int = 0 , ms:String = "")
{
this.title = title;
this.time = time;
this.ms = ms;
}
}
class ArrayUtil {
static public function random( max:Number, l:int ):Array {
var a:Array = [];
for ( var i:int = 0; i < l; i++ ) {
a.push( int(max * Math.random()) );
}
return a;
}
static public function almostSorted( max:Number, l:int ):Array {
var a:Array = [];
for ( var i:int = 0; i < l; i++ ) {
a.push( int( max * (i+Math.random()*10) / l) );
}
return a;
}
static public function copy( arr:Array ):Array {
var a:Array = [];
for ( var i:String in arr ) { a[i] = arr[i]; }
return a;
}
//==以下、各ソートのコードと解説==========================================================================================
/*
==挿入ソート(Insertion Sort)==========================================================================================
最善計算速度(Best) :O(n)
平均計算速度(Average) :O(n^2)
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(1)
安定性(stable) :Yes
各数値を前方の値と比較し、正しい位置に挿入するソート。
ランダムな配列では遅いが、ある程度整理された配列をソートするのはとても速い。
非常に単純なソートだが、使い道はわりとある。
*/
static public function insertSort( arr:Array, f:Function ):void {
for ( var l:int = arr.length, j:int = 1, i:int = 1, a:*, b:* = arr[1]; i < l; arr[i] = b, b = arr[ i = ++j ] )
while( i > 0 && !f( a = arr[i-1], b ) ) arr[i--] = a
}
/*
==二分挿入ソート(Dichotomic Insertion Sort)==========================================================================================
最善計算速度(Best) :O(nlogn)
平均計算速度(Average) :O(n^2) *ただし、挿入がO(1)で行える場合はO(nlogn)
最悪計算速度(Worst) :O(n^2) *ただし、挿入がO(1)で行える場合はO(nlogn)
メモリ使用量(Memory) :O(1)
安定性(stable) :No
挿入ソートの改良版のソート。
前の数値との比較を、二分探索で行うことで平均の比較回数を減らせる。
ただし、整理された配列のソートは遅くなるので、使い道は、あまり思い浮かばない。
*/
static public function dichotomicInsertionSort( arr:Array, f:Function ):void {
for ( var l:int = arr.length, j:int = 1, i:int = 0, s:int = 0, e:int = 1, a:*, b:*=arr[1]; j < l; s = 0, b = arr[e = ++j], i = e >> 1 ){
while ( s < e )
if ( f( a = arr[i], b ) ) i = ( (s = i + 1) + e) >> 1;
else i = (s + (e = i)) >> 1;
if ( i != j ) {
for ( var k:int = j; k > i; k-- ) arr[k] = arr[k - 1];
arr[i] = b;
}
}
}
/*
//==二分挿入ソート2(Dichotomic Insertion Sort2)==========================================================================================
最善計算速度(Best) :O(n)
平均計算速度(Average) :O(n^2) *ただし、挿入がO(1)で行える場合はO(nlogn)
最悪計算速度(Worst) :O(n^2) *ただし、挿入がO(1)で行える場合はO(nlogn)
メモリ使用量(Memory) :O(1)
安定性(stable) :No
挿入ソートの改良版のソートpart2。
二分探索で行うこと前に前回挿入を行った値と比較を行う。
ランダムな配列のソートは単純な二分挿入ソートと同程度に速く、整理された配列のソートもわりと速い。
*/
static public function dichotomicInsertionSort2( arr:Array, f:Function ):void {
for ( var l:int = arr.length, j:int = 1, i:int = 0, s:int = 0, e:int = 1, a:*=arr[0], b:*=arr[1]; j < l; s = 0, b = arr[e = ++j] ){
if( f( a, b ) ) s = i + 1, e = j;
else s = 0, e = i;
while ( s < e )
if ( f( a = arr[i], b ) ) i = ( (s = i + 1) + e) >> 1;
else i = (s + (e = i)) >> 1;
if ( i != j ) {
for ( var k:int = j; k > i; k-- ) arr[k] = arr[k - 1];
arr[i] = a = b;
}
}
}
/*
//==単純選択ソート(Selection Sort)==========================================================================================
最善計算速度(Best) :O(n^2)
平均計算速度(Average) :O(n^2)
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(1)
安定性(stable) :No
配列の中から一番小さい(大きい値)を探す。
↓
配列の先頭(末尾)に持ってくる。
↓
のこりの配列の中から一番小さい(大きい値)を探す。
↓
配列の先頭(末尾)に持ってくる。
を繰り返すソート。
アルゴリズムはすごく簡単、コードも簡単。
比較回数は多いが、要素の交換回数は少ない。
*/
static public function selectionSort( arr:Array, f:Function ):void {
for ( var i:int = 0, l:int = arr.length; i < l - 1; arr[k] = arr[i], arr[i++] = a )
for ( var j:int = i + 1, k:int = i, a:* = arr[i], b:*; j < l; j++ )
if ( !f( a, b = arr[j] ) ) a = b, k = j;
}
/*
//==短縮選択ソート(Short Selection Sort)==========================================================================================
最善計算速度(Best) :O(n)
平均計算速度(Average) :O(n^2)
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(n)
安定性(stable) :No
選択ソートの改良版ソート。
前回までに最小値(最大値)の交換を行った位置を記録しておくことで、探索範囲を減らしている。
要素の交換回数はそのまま、比較回数は単純選択ソートの半分程度に減らせることができる。
ある程度整理された配列をすばやくソート出来るという性質がある。
*/
static public function shortSelectionSort( arr:Array, f:Function ):void{
for( var l:int = arr.length, js:Vector.<int> = new Vector.<int>(), jl:int, i:int = 0, j:int = 1; l > 0; l-- ){
for ( var a:* = arr[i], b:*; j < l; j++ )
if ( f(a, b = arr[j] ) ) js.push(j), a = b, i = j;
arr[i] = arr[j - 1], arr[j - 1] = a;
if ( 0 < (jl = js.length) ){
j = js.pop();
if( 1 < jl ){ i = js[ jl - 2 ]; }
else i = 0;
}else j = 1, i = 0;
}
}
/*
//==バブルソート(Bubble Sort)==========================================================================================
最善計算速度(Best) :O(n)
平均計算速度(Average) :O(n^2)
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(1)
安定性(stable) :Yes
隣合う要素の交換を交換できなくなるまで繰り返す。
挿入ソート、選択ソートと同様、コードが単純で分かりやすいアルゴリズムの一つ。
ただし、あらゆる場面で挿入ソートに劣るので、使い道は無い。
*/
static public function bubbleSort( arr:Array, f:Function ):void {
var l:int = arr.length;
do for( var i:int = 1, loop:Boolean = false, el0:* = arr[0], el1:*; i < l; i++ )
if ( !f( el0, el1 = arr[i] ) ) arr[i - 1] = el1, arr[i] = el0, loop = true;
else el0 = el1;
while ( --l > 1 && loop );
}
/*
//==シェーカーソート(Cocktail Sort)==========================================================================================
最善計算速度(Best) :O(n)
平均計算速度(Average) :O(n^2)
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(1)
安定性(stable) :Yes
バブルソートの改良版。
隣接した要素の交換を、配列を往復するように行うソート。
有名なソート法ではあるが、アルゴリズムがまどろっこしい上に、あらゆる場面で挿入ソートに劣る。
実用性は全くない。
*/
static public function shakerSort( arr:Array, f:Function ):void {
var s:int = 0, e:int = arr.length-1;
do {
var loop:Boolean = false, i:int = s, el0:* = arr[s], el1:*;
while( ++i <= e )
if ( !f( el0, el1 = arr[i] ) ) arr[i - 1] = el1, arr[i] = el0, loop = true;
else el0 = el1;
if ( loop == false ) break;
loop = true, i = --e, el0 = arr[i];
while( --i >= s )
if ( !f( el0 = arr[i], el1 ) ) arr[i + 1] = el0, arr[i] = el1, loop = true;
else el1 = el0;
s++;
}while ( loop );
}
/*
//==コムソート(Comb Sort)==========================================================================================
最善計算速度(Best) :O(nlogn)?
平均計算速度(Average) :O(nlogn)?
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(1)
安定性(stable) :No
バブルソートを土台にした高速なソート。
5,6,9,8,1,0,3,4,7,2という配列の場合、以下のような手順でソートする。
1) 元の間隔5でみて、できる5つの配列に対して、バブルソートのように隣り合う要素の交換を1周だけ行う。
(この操作を「間隔5で櫛をかける」と呼ぶ。)
5,6,9,8,1,0,3,4,7,2
↓
5, 0
6, 3
9, 4
8, 7
1, 2
↓
0,3,4,7,1,5,6,9,8,2
2) 櫛の間隔を 5 -> 3 -> 2 というように減らしていく。
0,3,4,7,1,5,6,9,8,2
↓
0, 7, 6, 2
3, 1, 9
4, 5, 8
↓
0,1,4,6,3,5,2,9,8,7
↓
0, 4, 3, 2, 8
1, 6, 5, 9, 7
↓
0,1,3,5,2,6,4,7,8,9
3) 櫛の間隔が1になったら、バブルソート、または挿入ソートによって配列を完全にソートする。
0,1,3,5,2,6,4,7,8,9
↓
0,1,2,3,4,5,6,7,8,9
バブルソートや挿入ソートが大まかに整列された配列を高速でソート出来ることを利用したソート法。
櫛の間隔を調節することで、ランダムな配列に強くしたり、整列された配列に強くしたり、ソートの性質を変えることができる。
実装が楽で、ヒープソートやマージソートと同じレベルの速度が出せる。
なお、3)の段階ではバブルソートを使うのが一般的だが、挿入ソートを使ったほうが速くソート出来るので、下のコードでは挿入ソートを用いている。
*/
static public function combSort( arr:Array, f:Function ): void {
var l:int = arr.length, inc:int = l >> 1, j:int;
while( (inc = int(inc / 1.3 )) > 1 )
for(var s:int = 0; s < inc; s++)
for ( var i:int = s + inc, el0:* = arr[s], el1:*; i < l; i += inc )
if ( !f( el0, el1 = arr[i] ) ) arr[i - inc] = el1, arr[i] = el0;
else el0 = el1;
j = i = 1, el0 = arr[0];
while( i < l )
if ( !f( el0, el1 = arr[i] ) ) arr[i] = el0, arr[--i] = el1, i = ( i == 0 )? 0 : i-1, el0 = arr[i++];
else el0 = arr[j], i = ++j;
}
/*
//==シェルソート(Shell Sort)==========================================================================================
最善計算速度(Best) :O(n)?
平均計算速度(Average) :O(n(logn)^2)?
最悪計算速度(Worst) :O(n^1.25)?
メモリ使用量(Memory) :O(1)
安定性(stable) :No
櫛ソートと同様の高速化を挿入ソートを土台にして行ったソート。
櫛ソートでは、間隔を開けてできる配列に対して、隣り合う要素の交換を行ったが、
シェルソートでは、間隔を開けてできる配列を挿入ソートで完全にソートする。
櫛ソートと同じような特徴を持つが、櫛ソートよりやや低速。
*/
static public function shellSort( arr:Array, f:Function ): void {
var l:int = arr.length, inc:int = 1;
while ( inc < l ) inc = (inc * 3) + 1;
while ( (inc = (inc - 1) / 3) > 0 )
for ( var i:int = inc; i < l; arr[j] = b, i++ )
for ( var j:int = i, a:*, b:* = arr[i]; j >= inc && !f( (a = arr[j - inc]), b ); ) arr[j] = a, j -= inc;
}
/*
//==クイックソート(Quick Sort)==========================================================================================
最善計算速度(Best) :O(nlogn)
平均計算速度(Average) :O(nlogn)
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(logn)
安定性(stable) :No
単純かつ高速なソート。
配列から適当な値を取り出し、その値(ピボットと呼ぶ)より大きいか小さいかでその他の要素を2分していく。
このコードは、ピボットとして先頭にある要素を選択するという、もっとも単純なもの。
ランダムな配列をソートするのは高速だが、整列された配列のソートは非常に遅いという欠点がある。
*/
static public function quickSort( arr:Array, f:Function ):void {
for ( var jobs:Array = [ [0, arr.length] ], job:Array, s:int, e:int; job = jobs.pop(); ) {
if ( ( e = job[1]) - (s = job[0] ) < 2 ) continue;
for ( var i:int = s, j:int = e, pi:* = arr[s], el0:*, el1:*; ++i < j; ) if (! f( el0 = arr[i], pi ) ) while ( i < --j ) if ( !f( pi, el1 = arr[j] ) ) {
arr[i] = el1, arr[j] = el0;
break;
}
arr[s] = arr[--j], arr[j] = pi, jobs.push( [ j + 1, e ], [ s, j ] );
}
}
/*
//==クイックソート2(Quick Sort2)==========================================================================================
最善計算速度(Best) :O(nlogn)
平均計算速度(Average) :O(nlogn)
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(logn)
安定性(stable) :No
クイックソートの別バリエーション。
配列の先頭、最後尾、中央の値の中央値となる位置をピボットにすることで高速化している。
これなら整列された配列も問題ない速度でソート出来る。
ただし、特定の並びの配列に対してはやはり遅い。
*/
public static function quickSort2( arr:Array, f:Function ):void {
for ( var jobs:Array = [ [0, arr.length] ], job:Array, s:int, e:int, l:int, a:*, b:*, c:*; job = jobs.pop(); ) {
if ( (l = (e = job[1]) - (s = job[0] )) == 2 ) {
if (! f( a = arr[s], b = arr[s+1] ) ) arr[s] = b, arr[s + 1] = a;
}else if( l > 2 ){
var x:int = s, y:int = s + ((l + 1) >> 1) - 1, z:int = e - 1;
if ( f( a = arr[x], b = arr[y] ) ) {
if (! f( b, c = arr[z] ) ) {
arr[z] = b;
if ( f( a, c ) ) arr[y] = c;
else arr[x] = c, arr[y] = a;
}
}else{
if ( f( b, c = arr[z] ) ) {
arr[x] = b;
if ( f( a, c ) ) arr[y] = a;
else arr[y] = c, arr[z] = a;
}else arr[x] = c, arr[z] = a;
}
if ( l > 3 ) {
b = arr[y], arr[y] = arr[i = s + 1], arr[i] = b;
for ( var i:int, j:int = e - 1; ++i < j; ) if (! f( a = arr[i], b ) ) while ( i < --j ) if ( !f( b, c = arr[j] ) ) {
arr[i] = c, arr[j] = a;
break;
}
arr[s+1] = arr[--j], arr[j] = b, jobs.push( [ j + 1, e ], [ s, j ] );
}
}
}
}
/*
//==マージソート(Marge Sort)==========================================================================================
最善計算速度(Best) :O(nlogn)
平均計算速度(Average) :O(nlogn)
最悪計算速度(Worst) :O(nlogn)
メモリ使用量(Memory) :O(n)
安定性(stable) :Yes
配列を分割して、併合を繰り返していくソート。
例えば、43567218と並んでいる配列では、
4|3|5|6|7|2|1|8 と区画を分けて考えて、
隣あった区画が正しく並ぶように併合していく。
4|3|5|6|7|2|1|8
↓
34|56|27|18
↓
3456|1278
↓
12345678
ランダムな配列のソートではクイックソートにやや劣るが、十分速い。
また、配列の並びによる計算速度の変化が小さいという特徴がある。
等価な要素が元の順番を保ったままになるソート(=安定ソート)。
アルゴリズムの理解もしやすく、実用性の高いソート。
*/
static public function margeSort( arr:Array, f:Function ):void {
for ( var l:int = arr.length, c:int = 1, a:*, b:*; c < l; c += 2 )
if ( !f( a = arr[c - 1], b = arr[c] ) ) arr[c - 1] = b, arr[c] = a;
for( var w:int = 1; w < l; w <<= 1 )
loop: for( c = w; c < l; c += (w << 1) ){
var s:int = c - w, e:int = c + w, i:int = s, j:int = c;
if ( e > l ) { e = l }
for ( b = arr[j]; f( a = arr[i], b ); i++ ) if ( i == c ) continue loop;
for ( var x:int = c - 1, temp:Array = []; x > i; x-- ) temp.push( arr[x] );
for ( arr[x++] = b, b = arr[++j];; )
if( f( a , b ) ){
arr[x++] = a;
if( ++i == c ) break;
a = temp.pop();
}else{
arr[x++] = b;
if( ++j == e ){
while ( i++ < c ) arr[x++] = a, a = temp.pop();
break;
}
b = arr[j]
}
}
}
/*
//==内部マージソート(Marge Sort)==========================================================================================
最善計算速度(Best) :O(n^2) *ただし、挿入がO(1)で行える場合はO(nlogn)
平均計算速度(Average) :O(n^2) *ただし、挿入がO(1)で行える場合はO(nlogn)
最悪計算速度(Worst) :O(n^2) *ただし、挿入がO(1)で行える場合はO(nlogn)
メモリ使用量(Memory) :O(1)
安定性(stable) :Yes
マージソートの変形。
併合の時に挿入を用いることで、メモリの使用量を押さえたもの。
通常の配列のソートでは、普通のマージソートの方が圧倒的に速い。
安定な内部ソートが必要になった時に用いるのがよい。
リンクリストのソートなら高速で行えそう。
*/
static public function inPlaceMargeSort( arr:Array, f:Function ):void {
for( var l:int = arr.length, w:int = 1; w < l; w <<= 1 ){
for( var c:int = w; c < l; c += (w << 1) ){
var s:int = c - w, e:int = c + w;
if( e > l ){ e = l }
for( var i:int = s, j:int = c, a:* = arr[i], b:* = arr[j];; ){
if( f( a, b ) ){
if( ++i == j ){ break }
a = arr[ i ];
}else{
for( var k:int = j; k > i; k-- ){ arr[k] = arr[ k - 1 ] }
arr[ i++ ] = b;
if( ++j == e ){ break }
b = arr[ j ];
}
}
}
}
}
/*
//==ヒープソート(Heap Sort)==========================================================================================
最善計算速度(Best) :O(nlogn)
平均計算速度(Average) :O(nlogn)
最悪計算速度(Worst) :O(nlogn)
メモリ使用量(Memory) :O(1)
安定性(stable) :No
擬似的に木構造を作成して、その木構造を使ってソートする。
たとえば、
5,7,3,2,9,8,1,6,4 という配列なら
64
┌───┴┘
2981
┌─┴┘││
73──┴┘
┌┴┘
5
という木構造とみなせる。
配列の位置が木構造の位置になってるので、実際に木構造を作る必要はない。
ソートのアルゴリズムは以下のとおりである。
1) 交換を行い、親より大きい子がなくす。
64
┌───┴┘
2981
┌─┴┘││
73──┴┘
┌┴┘
5
24
┌───┴┘
6531
┌─┴┘││
78──┴┘
┌┴┘
9
2) 木の頭と末尾を交換し、木を1つ小さくする。
29
┌───┘
6531
┌─┴┘││
78──┴┘
┌┴┘
4
3) 先頭に持っていった数字を、親より大きい子がなくなるなるまで、移動する。
29
┌───┘
6531
┌─┴┘││
74──┴┘
┌┴┘
8 ※子二つのうち大きい方と比較し、子の方が大きければ交換していく。
4) 2),3)を繰り返す。
253189
┌─┴┘││
64──┴┘
┌┴┘
7
213789
┌─┴┘│
54──┘
┌┴┘
6
216789
┌─┴┘
34
┌┴┘
5
・・・
123456789
アルゴリズムを理解するのはやや難しいが、思いのほかコンパクトなコードにまとまる。
配列を逆向き並べているように見えるので効率が悪そうだが、マージソートと同程度に高速。
*/
static public function heapSort( arr:Array, f:Function ): void {
for ( var l:int = arr.length, j:int = 1, i:int = 1, a:*, b:* = arr[1], c:*; i < l; arr[i] = b, b = arr[ i = ++j ] )
while ( i > 0 && !f( b, a = arr[(i - 1) >> 1] ) ) arr[i--] = a, i >>= 1;
p:for( ;l-- > 0; arr[i] = a ){
for ( a = arr[l], arr[l] = arr[0], arr[0] = a, i = 0, j = 2; j < l; ) {
if ( f( c = arr[j], b = arr[j - 1] ) ) j--, c = b;
if ( f( c, a ) ) continue p;
else arr[i] = c, i = j, j = ( j << 1 ) + 2;
}
if ( --j < l && !f( c = arr[j], a) ) arr[i] = c, i = j;
}
}
/*
//==スムースソート(Smooth Sort)==========================================================================================
最高速度: O(n)
平均速度: O(nlogn)
最低速度: O(nlogn)
使用メモリ: O(1)
安定性:No
ヒープソート同様の擬似的な木構造を用いたソートだが,配列と木構造の対応がヒープソートとは異なる。
たとえば,
5,7,3,2,9,8,1,6,4,0 という配列なら
57
└┴32 81 0
└┴9└┴6
└──┴4
という木構造とみなす。この場合,要素9と要素1の二つの木ができる。
ヒープソートとは異なり木の数は複数にもなる。
また,各木の要素数は必ずレオナルド数になる。
ランダムな配列も,整列された配列も高速にソートできるらしいがアルゴリズムがわりと難しい。
勉強してみたけど挫折したのでコードは無し。
*/
/*
//==簡易版スムースソート(Easy Smooth Sort)==========================================================================================
最高速度: O(n)
平均速度: O(nlogn)
最低速度: O(nlogn)
使用メモリ: O(1)
安定性:No
スムースソートの良さをのこして,実装を少し簡単にしたソート法。
たとえば,
5,7,3,2,9,8,1,6,4,0 という配列なら
57 29 64
└┴3└┴8 └┴0
└──┴1
という2つの木構造とみなす。
スムースソートと同様,木の数は複数にもなる。
ソートのアルゴリズムは以下のとおりである。
1) 親より大きい子がなくなるよう交換を行う。
57 29 64
└┴3└┴8 └┴0
└──┴1
↓
53 21 04
└┴7└┴8 └┴6
└──┴9
2) 木の頭の中で最も大きいものを末尾に配置して木を小さくする。
53 21 04
└┴7└┴8 └┴6
└──┴9
↓
53 21 0 4 （9）
└┴7└┴8
└──┴6
※もっとも大きい値を選択する際に短縮選択ソートで使った高速化を行っている。
3) 交換を行った場合,子が親より小さくなるよう移動をする
53 21 0 4 （9）
└┴7└┴8
└──┴6
↓
53 21 0 4 （9）
└┴7└┴6
└──┴8
※子二つのうち大きい方と比較し子の方が大きければ交換,を繰り返す。
4) 2),3)を繰り返す。
53 21 0 4 （9）
└┴7└┴6
└──┴8
↓
43 21 0 （8,9）
└┴5└┴6
└──┴7
↓
43 01 （7,8,9）
└┴5└┴2
└──┴6
↓
43 01 （6,7,8,9）
└┴5└┴2
↓
23 0 1 （5,6,7,8,9）
└┴4
↓
21 0 （4,5,6,7,8,9）
└┴3
↓
01 （3,4,5,6,7,8,9）
└┴2
↓
0 1 （2,3,4,5,6,7,8,9）
↓
0,1,2,3,4,5,6,7,8,9
*/
static public function easySmoothSort( arr:Array, f:Function ): void {
for ( var i:int = 2, depth:int = 0, count:int = 0, s:int, t:int, n:int, l:int = arr.length; i < l; arr[j] = c ) {
for ( var d:int = depth, j:int = i, a:*, b:*, c:* = arr[i]; d >= 0; d-- ){
if ( f( a = arr[ s = j - (2 << d)], b = arr[ t = j - 1] ) ) s = t, a = b
if ( f( a, c ) ) break;
else { arr[j] = a, j = s; }
}
if ( 1 & ( count >> depth ) ) { depth++, i++; }
else { depth = 0, i += 3, count++; }
}
var rs:Vector.<int> = new Vector.<int>(), ds:Vector.<int> = new Vector.<int>();
for ( count = l + 1, i = -1, j = l - 1; count > 1; ) {
for ( var ex:int = 1; (count >> ex) != 1; ex++ ) {}
n = ( 1 << ex ) - 1; count -= n; i += n; rs.push(i); ds.push(ex - 2);
}
for ( var x:int = 0, y:int = 1, ys:Vector.<int> = new Vector.<int>(), yl:int; --l > 0; arr[j] = c ) {
a = arr[ j = rs[x] ]; d = ds[x];
for ( var rl:int = rs.length; y < rl; y++ ) { if ( f( a, b = arr[ i = rs[y] ] ) ) { ys.push(y), d = ds[y]; x = y; j = i, a = b; } }
for ( c = arr[l], arr[l] = a; d >= 0; d-- ){
if ( f( a = arr[ s = j - (2 << d)], b = arr[ t = j - 1] ) ) s = t, a = b
if ( f( a, c ) ) break;
else { arr[j] = a, j = s; }
}
if ( (yl = ys.length) ) {
y = ys.pop();
if ( yl > 1 ) x = ys[ yl - 2 ];
else x = 0;
}else{ y = 1, x = 0;}
i = rs.pop(); depth = ds.pop();
if ( depth >= 0 ) { i -= (n = ((--rl)?rs[rl-1]:-1)) + 1; rs.push( n += ( i >>= 1 ), n + i ); ds.push( depth - 1, depth - 1 ); }
}
}
//並列処理向けソート
/*
==奇遇転地ソート(Odd-Even Sort)==========================================================================================
最善計算速度(Best) :O(n)
平均計算速度(Average) :O(n^2)
最悪計算速度(Worst) :O(n^2)
メモリ使用量(Memory) :O(1)
安定性(stable) :Yes
バブルソートの改良ソート。
奇数番目とその次の偶数番目の比較／交換、偶数番目とその次の奇数番目の比較／交換を繰り返すアルゴリズム。
並列化が簡単で、並列化すると最悪でもn回の段階でソートできる。
*/
static public function oddEvenSort( arr:Array, f:Function ):void {
for (var c:int = 1, s:int = 1, l:int = arr.length, a:*, b:*; c >= 0 ; c--, s = 3 - s )
for ( var i:int = s; i < l; i += 2 )
if ( !f( a = arr[i-1], b = arr[i] ) ) arr[i - 1] = b, arr[i] = a, c = 1;
}
/*
//==バイトニックマージソート(Bitonic Marge Sort)==========================================================================================
最善計算速度(Best) :O(n(logn)^2)
平均計算速度(Average) :O(n(logn)^2)
最悪計算速度(Worst) :O(n(logn)^2)
メモリ使用量(Memory) :O(1)
安定性(stable) :No
マージソートを並列処理向けに改良したソート。
要素数8のときのソーティングネットワーク以下の通り。
┬┬─┬┬───┬─┬
┴┼┬┴┼┬──┼┬┴
┬┼┴┬┼┼┬─┴┼┬
┴┴─┴┼┼┼┬─┴┴
┬┬─┬┼┼┼┴┬─┬
┴┼┬┴┼┼┴─┼┬┴
┬┼┴┬┼┴──┴┼┬
┴┴─┴┴────┴┴
たった、O(logn)回の段階で終わる高速な並列ソート。
*/
static public function bitonicMargeSort( arr:Array, f:Function ):void {
for( var l:int = arr.length, w0:int = 1; w0 < l; w0 <<= 1 ){
for ( var c:int = w0; c < l; c += (w0 << 1) ) {
var e:int = c + w0;
if ( e > l ) { e = l; }
for ( var j:int = c, i:int, a:*, b:*; j < e; j++ )
if (! f( a = arr[i = c - (j - c) - 1], b = arr[j] ) ) arr[i] = b, arr[j] = a;
}
for ( var w1:int = (w0 >> 1); w1 > 0; w1 >>= 1 )
for ( c = w1; c < l; c += (w1 << 1) ) {
if ( (e = c + w1) > l ) e = l;
for ( j = c; j < e; j++ )
if (! f( a = arr[i = j - w1], b = arr[j] ) ) arr[i] = b, arr[j] = a;
}
}
}
/*
//==奇遇転地マージソート(Odd-Even Marge Sort)==========================================================================================
最善計算速度(Best) :O(n(logn)^2)
平均計算速度(Average) :O(n(logn)^2)
最悪計算速度(Worst) :O(n(logn)^2)
メモリ使用量(Memory) :O(1)
安定性(stable) :No
バイトニックマージソートよりさらに速い並列マージソート
要素数8のときのソーティングネットワーク以下の通り。
┬┬──┬──────
┴┼┬┬┼┬────┬
┬┴┼┴┼┼┬─┬─┴
┴─┴─┼┼┼┬┼┬┬
┬┬──┴┼┼┼┴┼┴
┴┼┬┬─┴┼┼─┴┬
┬┴┼┴──┴┼──┴
┴─┴────┴───
必要な段階は、バイトニックマージソートと同じO(logn)回だが、より少ない比較回数でソートできる。
*/
static public function oddEvenMargeSort( arr:Array, f:Function ):void {
for( var l:int = arr.length, w0:int = 1; w0 < l; w0 <<= 1 ){
for ( var c:int = w0; c < l; c += (w0 << 1) ) {
var e:int = c + w0;
if ( e > l ) { e = l; }
for ( var j:int = c, i:int, a:*, b:*; j < e; j++ )
if (! f( a = arr[i = j - w0], b = arr[j] ) ) arr[i] = b, arr[j] = a;
}
for ( var w1:int = (w0 >> 1); w1 > 0; w1 >>= 1 ){
for ( var s:int = 0; s < l; s += (w0 << 1) ){
var e0:int = s + (w0 << 1);
if ( e0 > l ) e0 = l;
for ( c = s + (w1 << 1); c < e0; c += (w1 << 1) ) {
if ( (e = c + w1) > l ) e = l;
for ( j = c; j < e; j++ ){
if (! f( a = arr[i = j - w1], b = arr[j] ) ) arr[i] = b, arr[j] = a;
}
}
}
}
}
}
//おまけ
/*
==シェレクションソート(Shellection Sort)========================================================================
最善計算速度(Best) :?
平均計算速度(Average) :?
最悪計算速度(Worst) :?
メモリ使用量(Memory) :O(n)
安定性(stable) :No
シェルソートの変形版。
挿入ソートの代わりに、短縮選択ソートを使う。
Shell SortとSelection SortのマッシュアップなのでShellection Sort
っていうダジャレがやりたかったので作ったソート。
シェルソートの方が速いので、使い道はほぼ無い。
*/
static public function shellectionSort( arr:Array, f:Function ):void{
var l:int = arr.length, inc:int = 1;
while ( inc < (l >> 4) ) { inc = (inc * 3) + 1; }
while ( (inc = (inc - 1) / 3 ) > 0 ) {
for ( var s:int = 0; s < inc; s++ )
for( var l2:int = l, js:Vector.<int> = new Vector.<int>(), jl:int, i:int = s, j:int = s + inc; l2 > 0; l2 -= inc ){
for ( var a:* = arr[i], b:*; j < l2; j += inc )
if ( f(a, b = arr[j] ) ) js.push(j), a = b, i = j;
arr[i] = arr[j -= inc], arr[j] = a ;
if ( 0 < (jl = js.length) ){
j = js.pop();
if( jl > 1 ) i = js[ jl - 2 ];
else i = s;
}else j = s + inc, i = s;
}
}
}
//非比較ソート
/*
==基数ソート(Radix Sort)====================================================================================================
uintの配列としてソートします、maxが最大の数値
*/
static public function uintRadixSort( arr:Array, max:uint = 0xFFFFFFFF, descending:Boolean = false ):void {
do{
var r:int, b:Array=[[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]];
for each( var v:uint in arr.splice( 0, uint.MAX_VALUE ) ) b[ ( v >>> r )& 255 ].push( v );
for ( var i:int = 0; i < 256; i++ ) arr.push.apply( null, b[ descending ? 7 - i : i ] );
}while ( max >>> (r += 8) );
}
}