# 問題解決力を鍛える！アルゴリズムとデータ構造

## 第12.5章〜

- 任意参加
- ファシリテーター: teruya

### 話す・書く順番決めルーレット

in Ruby

['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }

in JavaScript

const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]

### ファシリテーター決め方

- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく

### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）

当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分

### 勉強会時にやること

各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め

## 各自が書き込む場所

>[name=okura]

### 12.5 ソート（3）：クイックソート

Rubyのソートもクイックソートかなと思ってコード読んだけど、ヒープソートなのかなあ？

`array.c`

VALUE
rb_ary_sort_bang(VALUE ary)
{
    rb_ary_modify(ary);
    assert(!ARY_SHARED_P(ary));
    if (RARRAY_LEN(ary) > 1) {
        VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
        struct ary_sort_data data;
        long len = RARRAY_LEN(ary);
        RBASIC_CLEAR_CLASS(tmp);
        data.ary = tmp;
        data.receiver = ary;
        RARRAY_PTR_USE(tmp, ptr, {
            ruby_qsort(ptr, len, sizeof(VALUE),
                       rb_block_given_p()?sort_1:sort_2, &data);
        }); /* WB: no new reference */
        rb_ary_modify(ary);
        if (ARY_EMBED_P(tmp)) {
            if (ARY_SHARED_P(ary)) { /* ary might be destructively operated in the given block */
                rb_ary_unshare(ary);
                FL_SET_EMBED(ary);
            }
            ary_memcpy(ary, 0, ARY_EMBED_LEN(tmp), ARY_EMBED_PTR(tmp));
            ARY_SET_LEN(ary, ARY_EMBED_LEN(tmp));
        }
        else {
            if (!ARY_EMBED_P(ary) && ARY_HEAP_PTR(ary) == ARY_HEAP_PTR(tmp)) {
                FL_UNSET_SHARED(ary);
                ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
            }
            else {
                assert(!ARY_SHARED_P(tmp));
                if (ARY_EMBED_P(ary)) {
                    FL_UNSET_EMBED(ary);
                }
                else if (ARY_SHARED_P(ary)) {
                    /* ary might be destructively operated in the given block */
                    rb_ary_unshare(ary);
                }
                else {
                    ary_heap_free(ary);
                }
                ARY_SET_PTR(ary, ARY_HEAP_PTR(tmp));
                ARY_SET_HEAP_LEN(ary, len);
                ARY_SET_CAPA(ary, ARY_HEAP_LEN(tmp));
            }
            /* tmp was lost ownership for the ptr */
            FL_UNSET(tmp, FL_FREEZE);
            FL_SET_EMBED(tmp);
            ARY_SET_EMBED_LEN(tmp, 0);
            FL_SET(tmp, FL_FREEZE);
        }
        /* tmp will be GC'ed. */
        RBASIC_SET_CLASS_RAW(tmp, rb_cArray); /* rb_cArray must be marked */
    }
    ary_verify(ary);
    return ary;
}

`util.c`

void
ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
{
    struct bsd_qsort_r_args args;
    args.cmp = cmp;
    args.arg = d;
    qsort_r(base, nel, size, &args, cmp_bsd_qsort);
}

# define qsort_r(base, nel, size, arg, cmp) qsort_s(base, nel, size, cmp, arg)

結局、C11の`qsort_s`という関数を内部で呼んでいる。

https://www.kijineko.co.jp/qsort_s%E3%81%A8qsort_r%E3%81%A8qsort_s/

### 12.6 ソート（4）：ヒープソート

ヒープというデータ構造自体にソートが織り込まれている感じなのかな。

### 12.8 ソート（5）：バケットソート

これは割と簡単に自作できそう。

>[name=chen]

#### 12.5 ソート(3)：クイックソート & 12.6 ソート(4)：ヒップソート
- in-place性
- 再帰的なソート

1. 図12.7はめっちゃ理解しやすくて面白そうと思いますが、
再帰的なことは苦手なんですね...
3. 計算量の計算式：全く分からない:joy:

#### 12.8 ソート(5)：バケットソート

面白そうなことです！
コードを見ても何をしてるのがよく理解できないんですが、
自分で実装するとamazingだ！と思いました。

ちゃんとソートできました。

const MAX = 100000

function doArray(){
  let result = []
  for(let i = 0 ; i <= MAX ; i ++){
    result[i] = 0
  }
  return result
}

function BucketSort(a){
  let size = a.length
  let num = doArray()
  for(let i = 0 ; i < size; ++i){
    ++num[a[i]] //conut a[i] 
  }
  console.log('num=' + num)
  
  let sum = doArray()
  for(let v = 1 ; v < MAX ; ++v){
    sum[v] = sum[v - 1] + num[v]
  }
  console.log('sum=' + sum)
    
  let a2 = []
  for(let i = size - 1; i >= 0; --i){
    a2[--sum[a[i]]] = a[i]
  }
  
  a = a2
  return a
}

let a = [1,43,16,74,22,3,99]

let sortA = BucketSort(a)

console.log('sortA=' + sortA)
// num=0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0....
// sum=0,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4....
// sortA = 1,3,16,22,43,74,99


let b = [1,43,16,74,22,3,99,1,1]

let sortB = BucketSort(b)
console.log('sortB=' + sortB)
// num=0,3,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0
// sum=0,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,
// sortB=1,1,1,3,16,22,43,74,99

>[name=teruya]

> 12.5.3 乱択クイックソート

クイックソートの最悪計算量を落とせる工夫があるのは初めて知りました

> 12.8 バケットソート

は初めて聞きました！
O(NlogN)→O(N)は必ずしも劇的ではないですがおもしろいですね👀

>[name=tsujita]
- 　挿入ソート、マージソート、クイックソート、ヒープソートは入力要素の比較にのみ基づいて決定される比較ソートアルゴリズム
- 　バケットソートは予め入れ物を用意しておくイメージ、ソート対象の値が少ない時には有用
- 　https://qiita.com/shizen-shin/items/a8122cf6b3e5a6dc636c

## 振り返り

> [name=okura]

スリープソートが好きです。

ary = [1, 5, 4, 3, 2]
ary.each { sleep(_1); puts _1 }

> [name=teruya]

ビルトインライブラリがべんりすぎる

>[name=tsujita]

今日がこの本ラストだと思うと感慨深かったです

> [name=chen]

バケットソートは意外に面白いです！

- 【JavaScript】スリープソートの紹介と実装
https://cpoint-lab.co.jp/article/202207/23123/#:~:text=%E3%82%B9%E3%83%AA%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88%E3%81%AF%E6%B8%A1%E3%81%95%E3%82%8C,%E6%9B%BF%E3%81%88%E3%82%92%E3%81%99%E3%82%8B%E5%87%A6%E7%90%86%E3%81%A7%E3%81%99%E3%80%82

- javascript .sort()
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// Expected output: Array ["Dec", "Feb", "Jan", "March"]

const arr = ['boy', 'girl', 'apple', 'Tom']
arr.sort()
console.log(arr)
// output: ["Tom", "apple", "boy", "girl"]

## 終了後ファシリテーターがやること

RubyKaigi明け、5月19日（金）に今後の予定を決める予定です！