来る09/20はわんくま東京勉強会#24です。
ディレクターは はつね さん、
僕はソートをネタとしたLT(Ligtening Talk)に手ぇ挙げちゃいました。
LTってやったことないのよねー。
短い尺で喋るのってドキドキです、
10分以上あるなら尺の調整が利くんですけど
わずか5分ですからね。きっちり練習しとかんと...
さて、肝心のネタですが、なんにしましょ。
あんまり語られてないポい「ヒープソート」
を5分で語ってみましょうかしら。
早速ネタ仕込み。Visual Studio立ち上げてごりごり書く。
template<typename T>
void Sift(T data[], int L, int R) {
int i = L;
int j = 2*i + 1;
T x = data[L];
if ( j < R && data[j] < data[j+1] ) ++j;
while ( j <= R && x < data[j] ) {
data[i] = data[j];
i = j;
j = 2*j + 1;
if ( j < R && data[j] < data[j+1] ) ++j;
}
data[i] = x;
}
/*
* ヒープソート
*/
template<typename T>
void Sort(T data[],int n) {
int L = n / 2;
int R = n - 1;
while ( L > 0 ) Sift(data, --L, R);
while ( R > 0 ) {
T x = data[0];
data[0] = data[R];
data[R] = x;
Sift(data, L, --R);
}
}
コードの解説したってつまんない。さーてこれをどうすべか。
※ 昨日帰りがけに立ち寄った本屋でなにげに手にした一冊にあったヒトコト:
「スピーチなんかするな。ショーにしてしまえ」 いぃことゆー♪
[追記] STL使うとシュウたん並みに脱力します。o<\_
#include <iostream>
#include <algorithm>
int main() {
int data[] = { 9, 7, 5, 3, 1, 8, 6, 4, 2, 0 };
std::make_heap(data, data+10); // ぶっちゃけ
std::sort_heap(data, data+10); // こんだけ。
for ( int i = 0; i < 10; ++i )
std::cout << data[i] << ' ';
}