Lua で、クイックソート“qsort”

2016-05-16 :  PCクリニック
本文の前に、
-・・・ -・-
現時点での blogramのランクインカテゴリは、
7、2、0、0、1、 0、0、0、0、0(40)で、換算ポイント 88pt 。
「化学業界」「硝子業界」「FM COCOLO」「e-radio」、
「グルコサミン」「Firefox」bg値変動のみ。
「Perl」「C言語」「Python」「FM青森」全く変化無し。
・-・ - -・

さて、本文。

ソート処理に関しては、・・・・・

qsort
 標準ライブラリ関数 qsort は, stdlib.h の中で次のように宣言されており,
 ポインタ base を先頭とする配列(ただし,要素数は num,一つの要素のサイズ
 は size)の内容を,指定された比較方法 compareで昇順に並べ替える関数である.

void qsort(void *base, size_t num, size_t size,
int (*compare)(const void*, const void*))
 この関数の使用例は次のようになる.
 ・・・・・
 ・・・・・

とか、

C言語Tips集 - 配列やメモリ領域の内容を整列(sort)する
 C言語で配列やメモリ領域の内容を整列 (sort) するには
 stdlib.h の qsort 関数を使用します.
#include 

void qsort( void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *)
);
 qsort 関数は,base が指すオブジェクトの配列 (要素数が
 nmemb 個,各要素の大きさが size である配列) を compar が
 指す比較関数にしたがって整列する関数です.
  ちなみに qsort 関数の名前はクイックソート (quick sort) に
 由来しますが,内部でクイックソートアルゴリズムを使用してる
 保障はありません.(処理系定義)

 qsort 関数の引数をまとめると以下のようになります.
 ・・・・・
 ・・・・・

とか、多数存在する。


そうならば、と、真似をしてコード化してみた。
ffi.cdef[[
typedef int( __stdcall *comp )( int*, int* );
void qsort( void* base, int num, int size, comp func );
] ]
cb = ffi.cast( 'comp', function( x, y )
if ( x[0] < y[0] ) then return -1 --- 昇順
elseif( x[0] == y[0] ) then return 0
else return 1
end
end )
ary = ffi.new( 'int[9]' , { 9, 8, 7, 6, 5, 4, 3, 2, 1 } )
n = 9
for i=0,n-1 do print( ary[i] ) end --- 前
ffi.C.qsort( ary, n, 4, cb ) ----------------- こうですね!
for i=0,n-1 do print( ary[i] ) end --- 後
こんなモノ?

でも、実行したところ、
比較判定関数(コールバック関数?) の終盤でアボート???


原因究明に至らなかったので、
その昔、8年くらい前(2008年初め?)、それ以前(?)から使っていた「ActiveBASIC
でコード化したモノ。
それは、
ab.com コミュニティ ・ トピック - ソートロジック大会
にあるものを頂いていた。

これを、Lua に移植した:
--[[  ab.com コミュニティ ・ トピック - ソートロジック大会
http://www.activebasic.com/forum/viewtopic.php?f=1&t=285&start=15
'---------------------- Sort -------------------
'Dim SL[100] As DWord, SR[100] As DWord 'Stack 計算上は19?
'Quicksortノーマル版(非再帰):河川屋さんベース
'----------------------------------------------------------
これを移植。int 型配列の、昇順版
]]
-- int 配列 key[n1]~key[n2]
function QuickSort( key, n1, n2 )
local i, j, k, w, S, L, R
local SL = ffi.new( 'int[50]' )
local SR = ffi.new( 'int[50]' )
local idx = ffi.new( 'int[?]', n2+1 )
for i=0,n2 do idx[i]=i end
S=0; SL[0]=n1; SR[0]=n2
repeat
L=SL[S]; R=SR[S]; S=S-1
repeat
i=L; j=R; k=idx[math.floor((i+j)/2)]
repeat
while key[idx[i]] < key[k] do ---------- 昇順
i=i+1
end
while key[k] < key[idx[j]] do ---------- 昇順
j=j-1
end
if i<=j then
w=idx[i]; idx[i]=idx[j]; idx[j]=w
i=i+1; j=j-1
end
until i>j
if i R=j
until L>=R
until S<0
return idx
end
---------------------------------
n = 9
ary = ffi.new( 'int[9]' , { 10, 2, 3, 4, 51, 6, 7, 8, 9 } )
for i=0,n-1 do print( ary[i] ) end
idx = QuickSort( ary, 0, n-1 ) --------------- これ!
print( idx )
for i=0,n-1 do print( ary[idx[i]] ) end
これは、
所謂“インデックスソート”ですネ。

取り敢えず、整数型データ昇順にソートするものが出来た。
しかも、(より汎用的?)なインデックスソート

最終的に、実数型でも、降順でも対応できるようした。


function QuickSort( key, n1, n2, comp )
local i, j, k, w, S, L, R
local SL = ffi.new( 'int[50]' )
local SR = ffi.new( 'int[50]' )
local idx = ffi.new( 'int[?]', n2+1 )
for i=0,n2 do idx[i]=i end
S=0; SL[0]=n1; SR[0]=n2
repeat
L=SL[S]; R=SR[S]; S=S-1
repeat
i=L; j=R; k=idx[math.floor((i+j)/2)]
repeat
while comp( key[idx[i]] , key[k] ) do ---------- 昇順/降順
i=i+1
end
while comp( key[k] , key[idx[j]] ) do ---------- 昇順/降順
j=j-1
end
if i<=j then
w=idx[i]; idx[i]=idx[j]; idx[j]=w
i=i+1; j=j-1
end
until i>j
if i R=j
until L>=R
until S<0
return idx
end
---------------------------------
n = 9
ary = ffi.new( 'int[9]' , { 9, 8, 7, 6, 5, 4, 3, 2, 1 } ) --- 整数型
-- ary = ffi.new( 'double[9]' , { 9, 8, 7, 6, 5, 4, 3, 2, 1 } ) --- 実数型

for i=0,n-1 do print( ary[i] ) end

idx = QuickSort( ary, 0, n-1, |x,y| x<y ) --------- 昇順
-- idx = QuickSort( ary, 0, n-1, |x,y| x>y ) --------- 降順

for i=0,n-1 do print( ary[idx[i]] ) end
こんな感じ???


なお、「GSL - GNU Scientific Library
にも、
void gsl_sort_vector(gsl_vector* v)」や、
void gsl_sort_index(size_t* p, const double* data, size_t stride, size_t n)
があるが、
これは、実数型データの昇順ソートですネ。


本日はここまで。


Lua ( GSL Shell ) 学習は続く。


見ていただいた序でとは厚かましい限りですが、
お帰りに投票して頂けるとなお嬉しいです。 ⇒ blogram投票ボタン


160428
関連記事
スポンサーサイト

コメントの投稿

管理者にだけ表示を許可する

おきてがみ/blogram
blogram投票ボタン



おきてがみ

最新記事
カレンダー
03 | 2017/04 | 05
- - - - - - 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 - - - - - -
月別アーカイブ
カテゴリ
最新コメント
検索フォーム
リンク
プロフィール

<紙>

Author:<紙>
ようこそ。
「パソコンヲタクの雑記帳」
もろもろなことを綴っています。
パソコン ヲタクってねくら?
画像は kami でなく kani です。

カウンター(fc2、i2i) /Google Analytics


i2i(from 2010-08-24)
Total =
Today  =  
Yesterday=
アンチエイジング

Google Analytics
ブックマーク