アルゴリズム

たらい回し関数

たらい回し関数 竹内関数。ベンチマークに使われる。 それ以外に特に用途は無いらしい。 tarai(x, y, z){ if (x <= y) return y; else tarai(tarai( x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)); } 参考文献 C言語による最新アルゴリズム事典 (ソフト…

配列要素の回転

配列要素の回転 目的 配列の要素を循環させながらシフトさせたい。 例) a[10] = {0,1,2,3,4,5,6,7,8,9} 4だけシフト ▶︎{4,5,6,7,8,9,0,1,2,3} 解法 a : 配列の先頭から、シフト数分の要素の集合 b : a集合以外の要素の集合 とする。 例)arr[10] 4シフト a :…

Python練習(マージソート)

Pythonでマージソート マージソートは配列を二つに分け、各々でソートし、最後にマージしてソートする。 2つに分けた後のソートも同様な処理を再帰させて行うことができる。(分割統治法) マージソートは同じ値が存在した場合、配列の添字の順を維持すること…

Python練習(挿入ソート)

Pythonで挿入ソート 挿入ソートとは、ソート済みの要素に、順に要素を適切な位置へ挿入することで、 すべての要素をソートさせる考え方。計算量はO(N^2)。 ただし、バブルソートより高速であることが多い(値の入れ替え処理が少なく済むため) コード(Python) …

Python練習(選択ソート)

Python練習で選択ソート 選択ソートは要素の中で一番小さい値を探し出し、要素の先頭と入れ替える。 以後、決定した要素を除外し、繰り返す。 計算量はO(N^2)である。 コード(Python) #coding: UTF-8 #選択ソート x = [4,50,3,10,88,39,2,15] for i in range…

Python練習(バブルソート)

Python練習でバブルソート バブルソートは隣接するデータを比較していき、値の一番大きなものから順に値を決定 させていく。計算量はO(N^2)。 コード(Python) #coding: UTF-8 #バブルソート x = [4,50,3,10,88,39,2,15] i=len(x) while i > 0: j = 1 while j …