Help us understand the problem. What is going on with this article?

初心者でも分かるアルゴリズム解説(挿入ソート編)

はじめに

SEになってからアルゴリズムを考えた開発をしたことがなく、「エンジニアを名乗るからには基礎的なアルゴリズムを理解しておかないとまずいよな」と考え学習し始めたため備忘録として投稿を始めました。
しばらくはソート(挿入ソート、バブルソート、選択ソート、シェルソート)のアルゴリズム、計算量について書いていきます。
よろしくお願いします!

挿入ソートとは

入力データをソート済み部分列未ソート部分列に分け、未ソート部分列の先頭要素をソート済み部分列を昇順/降順になるように挿入するアルゴリズム。
要素をスライドさせてソートするため、安定なソートアルゴリズムと言います。
(ここでいう安定とは同じ番号が連続した場合、入力データと同じ要素順になることを言う)

アルゴリズム

イメージすると以下のようになります
insert_sort_algp-Page-1.jpg

計算量

ソート済み部分列の末尾から先頭にかけて挿入箇所を探索するため、最短で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にすればいいと思います。

def insert_sort(input_data):
  sort_data = list(input_data)
  for i in range(len(sort_data)):
    j = i - 1
    v = sort_data[i]
    while(j >= 0 and sort_data[j] > v):
      sort_data[j+1] = sort_data[j]
      j -= 1
    sort_data[j+1] = v
  print(sort_data)

所感

やはりアウトプットすると理解度が深まりますね。
ただ私の文章作成能力がないせいかめちゃめちゃ時間かかりましたけど。。。
そこは慣れかなと思うので続けていこうかなと思います。
あとアルゴリズムの説明で図を使いましたが、draw.ioというのを使いました。
今までパワポしか触ってこなかったマンなので一瞬使い方に戸惑いましたが、めちゃくちゃ便利です!
今度からこれ使います(ちょろい)

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした