データ構造とアルゴリズム：Qucikソート
重要度：高い!
インナー関数
関数の中であるまとまった処理を行う際に関数内に関数を定義することをインナー関数と呼ぶ。 関数内関数
コード
partionの部分で、pivotを配列の一番後ろの数値と決めて、その後左から一つづつpivotと比較して、pivotよりも小さければ一つ後ろの配列と入れ替える。その後右に移動して、pivotと比較して小さかったら入れ替える、大きかったらそのまま。というのを繰り返す。入れ替えを行う配列の要素はif numbers[j] <= pivot:でif文に引っかかった時はi += 1としているのでiの位置がどんどん右側にずれていく。if文に引っかかるたびにiの数値が大きくなり、交換する配列のindex番号が大きくなる。
最後に一番右に到達した後、移動していたiの番号の箇所にpivotの数値を入れる。 そうすることで下記のような状況が作れる。 - pivotの数字を挟んで - 右側はpivotより大きい数値 - 左側はpivotより小さい数値
最後に
_quick_sort(numbers, low, partition_index-1) _quick_sort(numbers, partition_index+1, high)
の部分で再起呼び出しを行い、partition_index-1は配列の区切りの一つ前partition_index+1の部分で配列の区切りの一つ後を示し、それらの左右の部分で再度大きさを比較する_quick_sortを呼び出して、ソートが完了するまで同じ操作を行う。
from typing import List
import random
def partition(numbers: List[int], low: int, high: int) -> int:
i = low - 1
pivot = numbers[high]
for j in range(low, high):
if numbers[j] <= pivot:
i += 1
numbers[i], numbers[j] = numbers[j], numbers[i]
numbers[i+1], numbers[high] = numbers[high], numbers[i+1]
return i+1
def quick_sort(numbers: List[int]) -> List[int]:
def _quick_sort(numbers: List[int], low: int, high: int) -> None:
if low < high:
partition_index = partition(numbers, low, high)
_quick_sort(numbers, low, partition_index-1)
_quick_sort(numbers, partition_index+1, high)
_quick_sort(numbers, 0, len(numbers)-1)
return numbers
nums = [random.randint(0, 1000) for i in range(10)]
print(quick_sort(nums))
[37, 93, 174, 191, 218, 702, 813, 854, 951, 975]
データ構造とアルゴリズム：insertion（挿入ソート）
重要度：高い
左から順に入れ替えていくが、一度入れ替えが起こった後その入れ替えた要素をtmp変数に格納し適切な位置に収まるまで左側の数値と比較して小さい値があったらさらに左へ、また次も小さいければさらに左へというように適切な位置まで左に送るソート。
どんどん左のものと比較して適切な位置に持っていく。
途中経過を確認。
range(1, len_numbers):と１から始めているので、j = i - 1としてjの初期値を0にしてあげる。その後、whileのなかで j -= 1とすることでpirntで出力しているように左側に一つづつ確認していくような処理を実現している。
from typing import List
import random
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
tmp = numbers[i]
j = i - 1
while j >= 0:
print(j, end=' ')
j -= 1
print()
nums = [random.randint(0,1000) for i in range(10)]
print(insertion_sort(nums))
コード
while j >= 0 and numbers[j] > tmp:となっているので、j >= 0か、numbers[j] > tmpのどちらかが満たされていないとwhile文を抜けることになる。一つづつずらしていき、tmpの数値がnumbers[j]より小さくなったら処理が終了する。
numbers[j+1] = numbers[j]では、左に一つづつずらしている時に、tmpの箱に入っている数値の箇所は空白になるが、それを比較して大きい数値はどんどん右に移動させていくので、numbers[j+1] = numbers[j]とするだけで十分で数値の入れ替えは必要ない。
whileを抜けたら、一番左まで到達したか、tmpの値が適切な位置まで到達した（これ以上小さい値は左側にない）＿
numbers[j+1] = tmpとしてtmpを配列に入れ戻す。
左側に一番小さい数値を入れていくことになるので、[3, 5, 1, 8 , 9, 4]のようなパターンで４を比較した時に1で止まらない？というのは起こり得ない。
4に到達するまでに、1は一番左の要素になっているため
from typing import List
import random
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
tmp = numbers[i]
j = i - 1
while j >= 0 and numbers[j] > tmp:
numbers[j+1] = numbers[j]
j -= 1
numbers[j+1] = tmp
return numbers
nums = [random.randint(0,1000) for i in range(10)]
print(insertion_sort(nums))
[127, 129, 358, 525, 614, 690, 710, 751, 847, 882]
データ構造とアルゴリズム：gnome sort（ノームソート）
重要度：低い
Bubbleソートと類似のソート手法で、左から順にみていき入れ替えた時にBubbleソートはそのまま右にずれるが、ノームソートでは入れ替えた後は左にずれる。
順番が正しい場合はスキップ
順番が正しくない場合はスイッチする。この後バブルソートでは右側に移動するがノームソートではスイッチした後に左側にずれるように動く。
そうすると2,1を比べた時に一番左側に2があるのでここもスイッチする。それ以上左にいけなくなったら再度右移動に戻って同じことを繰り返していく。
右側に行って、7,8を比べた時に順番が逆なので、入れ替える。その後、一度左に行って、5,7を比べた時に順番が正しいので右に進む。左側に小さい数を貯めていく方式なので、一度左に行って正しければそれ以上左に戻る必要はない。
右に大きい数字があったら正しい位置に配置されるまで左に向かい数値をスイッチしていき、右に一つもどって確認して一番右までスイッチがなく終了したらソートが完了する。
from typing import List
import random
def gnome_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
index = 0
while index < len_numbers:
if index == 0:
index += 1
if numbers[index] >= numbers[index-1]:
index += 1
else:
numbers[index], numbers[index-1] = numbers[index-1], numbers[index]
index -= - 1
return numbers
numbers = [random.randint(0,1000) for i in range(10)]
print(gnome_sort(numbers))
[87, 537, 811, 379, 306, 230, 853, 263, 861, 923]
データ構造とアルゴリズム：selection（選択ソート）
重要度：高い
左から一つづつ、一時的にtmp変数に格納して左から順にそれぞれの配列要素と大きさを比べ、tmpに入っている数値より小さい数値があればその数と入れ替える。その作業を一番右端まで行い、一番小さい数値が入っているインデックス番号の要素を配列の一番左の要素と入れ替える。
その後、２番目の数値を同じようにtmp変数に格納して、左から一番小さい値を除いて右に順次確認していく。 比較して小さい数値があれば、その数値と入れ替え、最後まで行った後に一番小さい数値の入っている要素と左から２番目の要素を入れ替えどんどん小さい値を左側の要素と入れ替えて、左側から順に小さい要素を揃えていく。
３と５を比較した時に３の方が小さいので５の要素と入れ替える。
from typing import List
def selectioin_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
min_idx = i
for j in range(i + 1, len_numbers):
if numbers[min_idx] > numbers[j]:
min_idx = j
numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
return numbers
nums = [random.randint(0, 1000) for i in range(10)]
print(selectioin_sort(nums))
[351, 532, 539, 550, 601, 686, 773, 871, 908, 995]
rubyで描くとこんな感じでできた
def selection_sort(numbers)
len_numbers = numbers.length
(0..len_numbers-1).each do |i|
min_idx = i
((i+1)..len_numbers-1).each do |j|
if numbers[min_idx] > numbers[j]
min_idx = j
end
end
numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
end
numbers
end
numbers = Array.new(10){ rand 1000 }
print selection_sort(numbers)
[71, 91, 136, 271, 352, 371, 566, 720, 861, 870]
データ構造とアルゴリズム：comb（コムソート）
重要度低い
combというのはクシという意味なので、クシを溶かしていくように、くしの幅を小さくしていくようにソートを行う手法。 Gap 7/1.3 = 5というのは櫛の幅だと考え、１番目と５番目の数値を入れ替えて入れ替える必要がなければ戻し、Gapを狭くして同じ作業を行なっていく。Gapの7というのは配列の個数。
前回の幅である５を分子として使用して、次の櫛の幅で同じ入れ替え確認作業を行う。
最終的に幅が１で入れ替え確認作業を行い、SwapフラグがFalseになったまま周回が終わるまで入れ替え作業を行なっていく。
from typing import List
import random
def comb_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
gap = len_numbers
swapped = True
while gap != 1 or swapped:
gap = int(gap / 1.3)
if gap < 1:
gap = 1
swapped = False
for i in range(0, len_numbers - gap):
if numbers[i] > numbers[i + gap]:
numbers[i], numbers[i + gap] = numbers[i + gap], numbers[i]
swapped = True
return numbers
# nums = [2, 9, 1, 8, 7 ,3, 5]
nums = [random.randint(0, 1000) for i in range(10)]
print(comb_sort(nums))
[169, 197, 217, 245, 328, 383, 555, 692, 824, 983]
データ構造とアルゴリズム：cocktail（シェーカーソート）
cocktail（シェイクソート）
カクテルをシェークするような動きをするのでこのような名前がつけられている。bubbleソートの改良版でbubbleソートにかなり類似しておりbubbleソートを振る、ようなイメージ。
まず、左から右に配列を見ていって小さければ入れ替え、というのはbubbleソートの時と同様。 ただ、swap = Falseというフラグがあり、その周回の時に入れ替えが起きたらSwapをTrueに変更する。一番右のlimitまできたらswapをFalseに直して、今度は右から左に数字を見る。
この時に左の方が大きければ、右と入れ替える。という作業を行う。一番大きい数値は最初の段階で一番右にくるのでlimitを一つ下げる。
右から左に来るときは、一番左の数値が一番小さい数値になるので左側のlimitを一つ上げるようにする。
一度もswapがTrueにならなかったらその時点でソートを完了して良い。そのため、swapが Trueにならない周回があったらその時点でソートが完了しているとみなしても良いため、全てのパターンを行う必要がなくBubbleソートよりも早く処理が完了する。
- まずswapの初期値がTrueなのでwhile swappedの箇所でwhilteのloopに入る。
- 通常のbubbleソート同様に左の数値が大きければ右の数値と入れ替えるというのを１重のfor文で実現する
- ①の最後でもしswappが起こればswappedフラグをTrueにする。
- この時点で、swappedがFalseのままであれば、その時点でソート完了し、breakとなる
- 初期でendを−１している理由は、最初のfor文で一番後ろに最大値が移動するので一番後ろまで処理する必要がないから
- そのご②に入る
- ②に入る前にend - 1をしてあげることで、limitを一つずらす
for i in range(end-1, start-1, -1):というfor文は配列を逆順に入れる作業をしている- この逆順にする作業で、for文を逆から読み込ませる作業を行なっている。実際に行っているのは通常のbubbleソートの逆順にしたバージョンである。
- 最後にもしswapped = Trueになれば再度一番上に戻り①からやり直しswapped = Falseのまま続くまで行う。
from typing import List
def cocktail_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
swapped = True
start = 0
end = len_numbers - 1
while swapped:
swapped = False
# 右方向に進むときの for loop
# for①=============================start
for i in range(start, end):
if numbers[i] > numbers[i+1]:
numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
swapped = True
# for①=============================end
# swappが変更されなければfalseのままなのでここで処理が終了
if not swapped:
break
swapped = False
end = end - 1
# for②=============================start
for i in range(end-1, start-1, -1):
if numbers[i] > numbers[i+1]:
numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
swapped = True
# for②=============================end
start = start + 1
return numbers
import random
arry = [random.randint(0, 100) for i in range(10)]
print(cocktail_sort(arry))
[0, 5, 36, 44, 53, 55, 68, 83, 84, 96]
このサイトのgif?がすごくわかりやすいのだが、右に行くときは大きいものを一番右に押しやる作業、左に行くときは小さいものを一番左に押しやる作業を行なっているのがわかる。 眺めていられるシェーカーソートのシミュレーション|JavaScript
データ構造とアルゴリズム：本編
アルゴリズムの重要性
GAFAやシリコンバレーの企業面接には絶対にアルゴリズムのコーディング試験があり、1秒でも処理が早くなるのであればアルゴリズムを早い方に書き換えたほうが良い。車の自動運転など瞬間の判断に関わるものは特に反応速度が重要視されているので、アルゴリズムについて精通していたほうが良い。
データ構造
- データをどのように格納するのか
- どのような格納順で実装すると処理が早くなるのかなどの構造のこと
Big O Notation (Big O 記法)
learn-programing.hatenablog.jp
安定ソート
安定ソートとは
ソート判定において、同一であると判断された入力データの順序がソート後も変わらない
元の配列のソート順は変わらない
ex) (2, Bill) , (2, June) という要素はstable sortでは元の順番が変わっていないが、unstable sortではそれぞれの順番が変わっている。
ソート
bogoソート
重要度：低い learn-programing.hatenablog.jp
bubbleソート
重要度：高い learn-programing.hatenablog.jp
cocktail（シェーカーソート）
重要度：低い learn-programing.hatenablog.jp
comb（シェーカーソート）
重要度：低い learn-programing.hatenablog.jp
selection（選択ソート）
重要度：高い
