1. arthur_maki

    No comment

    arthur_maki
Changes in body
Source | HTML | Preview
@@ -1,43 +1,44 @@
## はじめに
SEになってからアルゴリズムを考えた開発をしたことがなく、「エンジニアを名乗るからには基礎的なアルゴリズムを理解しておかないとまずいよな」と考え学習をし始めたため備忘録として投稿を始めました。
しばらくはソート(挿入ソート、バブルソート、選択ソート、シェルソート)のアルゴリズム、計算量について書いていきます。
よろしくお願いします!
## 挿入ソートとは
入力データを`ソート済み部分列`と`未ソート部分列`に分け、未ソート部分列の先頭要素をソート済み部分列を昇順/降順になるように挿入するアルゴリズム。
要素をスライドさせてソートするため、安定なソートアルゴリズムと言います。
(ここでいう安定とは同じ番号が連続した場合、入力データと同じ要素順になることを言う)
## アルゴリズム
イメージすると以下のようになります
![insert_sort_algp.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/569863/ba02bf24-ae62-ceb0-93a0-c0d532f8b4c4.jpeg)
## 計算量
`ソート済み部分列`の末尾から先頭にかけて挿入箇所を探索するため、最短で1回、最長で$N-1$回の探索が必要となる。
したがって、入力データの探索回数を一般化すると$1+2+・・・+N-1=(N-1)N/2$回となる。
これをオーダー表記に当てはめると、$O((N-1)N/2)$となるが、オーダー表の性質の一つに`影響力が一番強い項以外無視する`があるため、$O(N^2)$となる。
しかし、上記オーダーは入力データがソートしたい順とは逆になってる場合で、既にソート順が同じ場合は入力データの探索回数全て1回で済むため$1+1+1+・・・+1=N$回となり、オーダー表記も$O(N)$となる。
-## コード
+## コード(昇順の場合)
`未ソート部分列`の先頭要素を表す変数`i`と`ソート済み部分列`に挿入する値`v`と`ソート済み部分列`で昇順/降順を探索するための変数`j`を使用すると以下のようになる。
上記の計算量で言う$1+2+・・・+N-1$回と言うのは`while`内での処理の数ですね
+また、以下は昇順にソートするコードですが、降順にしたい場合は`input_data[j] < v`にすればいいと思います。
```python
def insert_sort(input_data):
for i in range(len(input_data)):
j = i - 1
v = input_data[i]
while(j >= 0 and input_data[j] > v):
input_data[j+1] = input_data[j]
j-=1
input_data[j+1] = v
return input_data
```
## 所感
やはりアウトプットすると理解度が深まりますね。
ただ私の文章作成能力がないせいかめちゃめちゃ時間かかりましたけど。。。
そこは慣れかなと思うので続けていこうかなと思います。
あとアルゴリズムの説明で図を使いましたが、`draw.io`というのを使いました。
今までパワポしか触ってこなかったマンなので一瞬使い方に戸惑いましたが、めちゃくちゃ便利です!
今度からこれ使います(ちょろい)