挿入ソート(C言語、Go言語)

C言語で挿入ソートです。挿入ソートは遅いけれどわかりやすい。カードで考えると、(ソート済の)並んだカードの正しい位置に、残ったカードをそれぞれ一枚ずつ挿入していく(なのでそれもソート済になっている)というやり方で全体をソートします。
insertion_sort.c

#include <stdio.h>

void insertion_sort(int ar[], int len) {
    int i, j, key;
    
    for (j = 1; j < len; j++) {
        key = ar[j];
        i = j - 1;
        while (i >= 0 && ar[i] > key) {
            ar[i + 1] = ar[i];
            i--;
        }
        ar[i + 1] = key;
    }
}

int main () {
    int ar[] = {3, 1, 5, 2, 9, 7, 0};
    int len = sizeof ar / sizeof(int);
    
    insertion_sort(ar, len);
    
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d, ", ar[i]);
    }
    printf("\b\b]\n");
    
    return 0;
}

 
Ruby FFI 化してみる。C言語だけで配列をシャッフルしてベンチマークを取るのが面倒くさい。
insertion_sort_ffi.rb

require 'ffi'

module MyModule
  extend FFI::Library
  ffi_lib "./insertion_sort.so"
  attach_function :insertion_sort, [:pointer, :int], :void
end

p ar = [*0..10].shuffle
size = ar.size
pointer = FFI::MemoryPointer.new(:int, size)
pointer.put_array_of_int(0, ar)

MyModule.insertion_sort(pointer, size)
p pointer.read_array_of_int(size)

ベンチマーク

require 'ffi'
require 'benchmark'

ar = [*0..10000].shuffle

Benchmark.bm do |x|
  x.report {MyModule.insertion_sort(pointer, size)}
end

結果。

       user     system      total        real
   0.090000   0.000000   0.090000 (  0.090020)

pure Ruby からほぼ14倍くらいの高速化ということになるのかな(参照)。まったく同様のコードの場合と比較すれば、25倍以上速くなったことになる。ちなみに Ruby 組み込みの sort メソッドを使えば、この C言語FFI)の場合と比べものにならないくらい速い。何ソートなのだろうな。


※参考
Ruby FFI でエラトステネスの篩 - Camera Obscura
 

Go言語版

C と似た Go言語だとこんな感じかな。
insertion_sort.go

package main
import "fmt"

func insertion_sort(ar []int) []int {
    for j := 1; j < len(ar); j++ {
        key := ar[j]
        i := j - 1
        for i >= 0 && ar[i] > key {
            ar[i + 1] = ar[i]
            i--
        }
        ar[i + 1] = key
    }
    return ar
}

func main() {
    ar := insertion_sort([]int{3, 1, 5, 2, 9, 7, 0})
    fmt.Println(ar)
}

明らかに C言語っぽいのだけれど、随分とすっきりしていますね。出力もラクだし。自分はこちらの方が好きだなあ。
しかし Ruby から呼び出すのはわからんね。FFI を使おうと思ったが、Go のスライスにどうやって渡したらいいかわからなかった。