実装 import hashlib class HashTable(object): from typing import Any def __init__(self, size=10): super().__init__() self.size = size self.table = [[] for _ in range(self.size)] def hash(self, key) -> int: # hashlib.md5で文字列をエンコード…

単方向連結リストはnextのみを管理していたが、双方向は名前の通り双方向の連結を管理している。 解説 単方向との違いは class Node(object): def __init__(self, data: Any, next_node: Node = None, prev_node: Node = None): super().__init__() self.dat…

単方向リンク 画像のように、データを一列に持っているデータ構造で、リンクの一番後ろにデータをどんどん追加したり、一番最初にデータを追加したりということを行う。 appendでデータ構造の一番後ろに新しくNodeを追加できるようにしている。 insertではデ…

重要度：高い! インナー関数 関数の中であるまとまった処理を行う際に関数内に関数を定義することをインナー関数と呼ぶ。 関数内関数 コード partionの部分で、pivotを配列の一番後ろの数値と決めて、その後左から一つづつpivotと比較して、pivotよりも小さ…

重要度：高い 左から順に入れ替えていくが、一度入れ替えが起こった後その入れ替えた要素をtmp変数に格納し適切な位置に収まるまで左側の数値と比較して小さい値があったらさらに左へ、また次も小さいければさらに左へというように適切な位置まで左に送るソ…

重要度：低い Bubbleソートと類似のソート手法で、左から順にみていき入れ替えた時にBubbleソートはそのまま右にずれるが、ノームソートでは入れ替えた後は左にずれる。 順番が正しい場合はスキップ 順番が正しくない場合はスイッチする。この後バブルソート…

重要度：高い 左から一つづつ、一時的にtmp変数に格納して左から順にそれぞれの配列要素と大きさを比べ、tmpに入っている数値より小さい数値があればその数と入れ替える。その作業を一番右端まで行い、一番小さい数値が入っているインデックス番号の要素を配…

重要度低い combというのはクシという意味なので、クシを溶かしていくように、くしの幅を小さくしていくようにソートを行う手法。 Gap 7/1.3 = 5というのは櫛の幅だと考え、１番目と５番目の数値を入れ替えて入れ替える必要がなければ戻し、Gapを狭くして同…

cocktail（シェイクソート） カクテルをシェークするような動きをするのでこのような名前がつけられている。bubbleソートの改良版でbubbleソートにかなり類似しておりbubbleソートを振る、ようなイメージ。 まず、左から右に配列を見ていって小さければ入れ…

アルゴリズムの重要性 GAFAやシリコンバレーの企業面接には絶対にアルゴリズムのコーディング試験があり、1秒でも処理が早くなるのであればアルゴリズムを早い方に書き換えたほうが良い。車の自動運転など瞬間の判断に関わるものは特に反応速度が重要視され…

アルゴリズムの処理速度を可視化したもの。 O(log(n)) # O(log(n)) def func2(n): if n <= 1: return else: print(n) func2(n/2) func2(10) 10 5.0 2.5 1.25 O(n) # O(n) def func3(numbers): for num in numbers: print(num) func3(range(1,10)) 1 2 3 4 5 …

bogo（ボゴソート） ボゴソートはシャッフルに並び替えた後にそのソートが正しく並び替えられているかを確認するソート手法。 def in_orderでは、左側の数字が右側の数字(i+1番目）よりも大きければその時点で並び替えは失敗しているので、return Falseとい…

一番左側から、配列の個数分forループを行い、limitまで到達したら再度左に戻ってきて同じ処理を行う。 その際にlimitの位置は1つ左に移動する。 for j in range(len_numbers - 1)の部分でlimitの移動を再現している。 一番大きい数字は１週目で一番右にくる…