今日のアルゴリズム(JS実装) 〜Interpolation Search〜

// どうも、わくばです！ 今日はInterpolation Searchです。このアルゴリズムはBinary Searchの改造版で基本的な考え方は同じです。したがってソート済みの配列に適用する点は同じです。では何が違うのかというと、Binaryでは真ん中で半分にしていましたが、Interpolationでは分割点をもっと正確に計算しているという点です。確かに、何も考えずに真ん中で分けるのはあまりスマートではないですよね。せっかくソート済みなんだからもう少し絞れるだろ、というわけです。「あいさつ」という言葉を国語辞典で調べる場合、真ん中を開くことはしませんよね。あ行のように明らかに近いところ…

今日のアルゴリズム(JS実装)〜Jump Search〜

// どうも、わくばです！ 今日は Jump Searchです。こちらもソート済みの配列を検索するアルゴリズムです。単純に言うとLinear Searchを端折った感じです。まず決まったintervalで飛び飛びに進んで探索をします。どのintervalにあるかわかったらその中でLinear Searchをして終わりです。 コードは以下のようになりました。 const jumpSearch = (array, value) => { let { length } = array let interval = Math.floor(Math.sqrt(length)); //これらは区画の両端。…

今日のアルゴリズム(JS実装)〜Binary Sort〜

どうも、わくばです！ 今日はBinary Sortです。ソートが前提の処理ですが、前回のLinear searchより速いと思います。 仕組みはこんな感じ 基準値を決める 基準値と探している値を比べる 基準値より大きければその基準値より上に的を絞る 基準値より小さければその基準値より下に的を絞る 一個になったらそれが答え 半分ちょを繰り返して探していくってことですね。 const binarySearch = (array, value) => { //まずソート。以前の記事を参照 const sortedArray = quickSort(array); //上限と下限を定義する //ここか…

今日のアルゴリズム(JS実装)〜Linear Search〜

// どうも、わくばです！ Sortに関してはある程度有名なものをやり終えたので、Searchに入ろうと思います。 今日はLinear Searchです。一番簡単なサーチだと思います。 コードはこんな感じです。 function linearSearch(array, value){ let results = [] for(let i = 0; i < array.length; i++){ if(arr[i] === value){ results.push(i) } } return results ? results : -1 } console.log(linearSearch([1…

今日のアルゴリズム(JS実装)〜Radix Sort〜

// どうも、わくばです！ 今日はRadix Sortです。Bucket Sortに似てますね。Radixというのは基数とか根とか底とかいくつか訳がありますが、この例ではn進法のnのことです。 Radix Sortを簡単に説明すると、例えば10進法で考えるなら 0−9の計10個のバケットを準備する 配列を全部スキャンし、各要素の1桁目の値について0−9に分類してバケットに入れる(345という要素ならバケット5に入れる) 2を桁を上げて繰り返す。 といった感じです。比較ベースではないタイプのソートです。 コードはこんな感じになりました。 radixBaseはn進法のnのことです const ra…

今日のアルゴリズム(JS実装)〜Bucket Sort〜

どうも、わくばです！ 今日はBucket Sortを勉強しました。バケツを用いた分割統治アルゴリズムで、Counting Sort の一般化と考えられます。実際、バケツサイズを1とすると同じ値のものだけが同じバケツに集約されていくので、Couting Sortと同様の処理になります。 バケツに分割して、それぞれのバケツでソートを実行し、統合するという典型的な仕組みです。 コードはこんな感じです。 //bucketSize : バケット一個あたりの要素数 const bucketSort = (array, bucketSize = 5) => { if (array.length < 2) {…

今日のアルゴリズム(JS実装)〜Counting Sort〜

// どうも、わくばです！ 先日。E資格に申し込んだと言ったのですが、試験会場が都心しか空いていないことと、その他大学の実習の都合などいろいろ加味した結果、キャンセルして見送ることにしました。 JDLA認定は二年間有効なので、また機を見て受験しようと思います。 一応報告でした。 さて今日勉強したのは、Counting Sortです。まず出現回数をカウントし、その情報を回数と値がペアになるように別の配列に保持しておきます。今回は出現回数をvalue、何の値かをindexとして配列を作成しています。値をindexとすることで自然にソートされます。 以下がコードです。 const countingS…

今日のアルゴリズム(JS実装)〜Shell Sort〜

// どうも、わくばです！ 今日はShell Sortを学びました。これはInsertion Sort の応用なのでコードを見てイマイチピントこなかった方は以前書いたInsertion Sortをぜひ参考にしてみてください*1 Shell Sortは飛び飛びでグループを形成し、グループごとにInsertion Sortを繰り返していくソートです。由来に関しては諸説あり、飛び飛びの間隔が徐々に狭まっていく様子が、貝殻のすぼまっていく形状を想起させるという説と、シンプルに「ドナルド=シェル」という方が考案したからという説がありました。 コードはこんな感じです。 const shellSort = …

Big O notation の計算原理についてちゃんと調べてみた

// どうも、わくばです！ アルゴリズムをいくつか勉強しているうちにBig O notationに関してだいぶ適当だったと感じてのでちゃんと調べてみました。が、結局わりと適当でオッケーみたいですね笑 MITのサイトや各種プログラミング学習サイトから引用しながら地味&&ラフに説明させていただきます。 まず気になっていたのが、\(\Theta()\)とか\(\Omega()\)とかの記号です。\(O()\)しか見聞きしたことなかったので一旦調べてみました。 freeCodeCampの記事では以下のようにありました。 Big O: “f(n) is O(g(n))” iff for some con…

今日のアルゴリズム(JS実装)〜Quick Sort〜

// どうも、わくばです！ E資格の申し込みを完了しました。2万は高いなあww もともとなんでE資格を受けようと思ったかというと、プログラミングの勉強を始めたとき医学と親和性高いものってことで人工知能やデータサイエンスの領域に的を絞っていて、背水の陣を敷くために8万のJDLA認定講座に登録したのが事の発端なんです。 なんて消極的な受験動機なんだ(笑) 勉強過程でアプリ開発の方に興味がそれまして、いまやE資格は「早く終わらせたいタスク」みたいな位置づけになってしまいました。10万近く使ったので、貧乏大学生としてはなんとしても意味あるものとして終えたいわけです(笑) 無駄話はさておき今日のアルゴリ…

今日のアルゴリズム(JS実装)〜Merge Sort〜

// どうも、わくばです！ 今日はJDLA認定講座の最後の試験でした。無事合格しましたので、これでやっとE資格試験を受験できます。 なんでこんなにめんどくさいのだ（笑） 機械学習は統計的な処理もしっかり含まれていて、医学でも役立つので何れにせよ頑張りきろうと思います。 さて今日のアルゴリズムですが、Merge Sortです。いくつかアルゴリズムをコードに起こしてきましたが、アルゴリズムのぱっと見の印象では意外と複雑さの検討がつきにくいですね。 ソート系は難易度低い印象ですがBubble Sortや今回のMerge Sortなど、所見でコードを書こうとするとなかなかしんどいです（笑） Merge…

今日のアルゴリズム(JS実装)〜Insertion Sort〜

// どうも、わくばです！ 今日はInsertion Sortです。自分より前の要素を比較していって、自分より小さいものが現れたらその後ろに挿入するというアルゴリズムです。 コードは以下のような感じです。 const insertionSort = array => { for (let i = 1; i < array.length; i++) { //jの位置から比較しながら前に戻っていく let j = i; let temp = array[i]; //tempより小さいものがでてくるまでループ while (j > 0 && array[j - 1]> temp) { //自分より大…

今日のアルゴリズム(JS実装)〜Selection Sort〜

// どうも、わくばです！ 今日はSelection Sort を学びました。今回はシンプルです。 このサイトが非常にわかりやすいのでぜひ：Selection Sort - InterviewBit コードはこんな感じになりました。 function selectionSort(array, size){ const { length } = array; for (let i=0; i< length; i++){ let minIdx = i; for(let j =i+1; j < length; j++){ if(array[i]>array[j]){ minIdx = j; } } …

今日のアルゴリズム〜Binary Heap〜

どうも、わくばです！ 昨日はJDLA認定講座の数学試験があったので、お休みしました(笑) 今日はBinary Heapです。正直コードに落とすのがかなり複雑で時間がかかっていしまいました。ヒープがどんなデータ構造なのかについてはページの最後に参考を用意しておいたのでそちらを御覧ください。*1 結局は優先キューなので、「自由に追加できる」「先頭から最小のものを取り出せる」が実現できれば良く、重要なのは挿入や抽出をした後の配置換えの部分になるかなと思います。以下では一つのクラスとしてまとめて実装しています。 Minimum HeapとMax Heapどちらでも大した違いはありませんが、今回はMin…

今日のアルゴリズム〜Bubble Sort〜

// どうも！わくばです！ 今日から1日1アルゴリズムずつ記事にしていこうかなと思います。今までなんとなく避けてきたんですがそろそろそうも行かなくなってきたので、、、 普段codewarsというサイトでコーディングの勉強をしているんですが、上級になると結構難しくなるんですよね。codewarsではレベルのことをkyuといって、そのkyuが上がってくるとどうにも素人の発想では回答できない問題も増えてきます。kyuが上がるのに比例して1問にかかる時間が長くなってきまして、そろそろ真面目にアルゴリズムを勉強しておかないと、この先いくら時間があってもてりないのでは、、、というわけです(笑) 勉強の手順…