LoginSignup
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@otupy(py 乙)

100日後にエンジニアになるキミ - 60日目 - プログラミング - データ構造とソートアルゴリズムについて

Last updated at Posted at 2020-05-19

昨日までのはこちら

100日後にエンジニアになるキミ - 59日目 - プログラミング - アルゴリズムについて

100日後にエンジニアになるキミ - 53日目 - Git - Gitについて

100日後にエンジニアになるキミ - 42日目 - クラウド - クラウドサービスについて

100日後にエンジニアになるキミ - 36日目 - データベース - データベースについて

100日後にエンジニアになるキミ - 24日目 - Python - Python言語の基礎1

100日後にエンジニアになるキミ - 18日目 - Javascript - JavaScriptの基礎1

100日後にエンジニアになるキミ - 14日目 - CSS - CSSの基礎1

100日後にエンジニアになるキミ - 6日目 - HTML - HTMLの基礎1

データ構造

アルゴリズムを学ぶ上で重要なのがデータ構造です。
アルゴリズムは手順であるので、どのようなデータをどのように操作するのかと言った
データの構造もアルゴリズムでは重要な項目となります。

リスト

Pythonのリスト型は配列形式のデータ型でインデックスを用いて
順番でアクセスすることができます。

リスト型では様々なデータを要素として格納することができ
要素の追加、変更、入れ替え、削除を行うことができます。

# リストの定義
l = [1,2,3,4,5]
print(l)

# 要素の参照
print(l[0])

# 要素の変更
l[1] = 8
print(l)

# 要素の追加
l.append(6)
print(l)

# 要素の削除
l.pop(3)
print(l)

# 要素の挿入
l.insert(4,9)
print(l)

# 要素の入れ替え
l[0], l[3] = l[3], l[0]
print(l)

[1, 2, 3, 4, 5]
1
[1, 8, 3, 4, 5]
[1, 8, 3, 4, 5, 6]
[1, 8, 3, 5, 6]
[1, 8, 3, 5, 9, 6]
[5, 8, 3, 1, 9, 6]

スタックとキュー

スタックもキューもデータの取り扱い方法の１つになります。

スタック
・データ追加は列の先頭から、データ取り出しも列の先頭から
・後入れ先出しLIFO(Last-In-First-Out）
・スタックにデータを入れることをプッシュ(push)、取り出すことをポップ(pop)と言う

キュー
・データ追加は列の末尾、データの取り出しは列の先頭から
・先入れ先出し(トコロテン方式）FIFO (First-In-First-Out)
・キューにデータを入れることをエンキュー(enqueue)、取り出すことをデキュー(dequeue)という

参考：wikipedia

Pythonではリスト型やçで実現することができます。

スタック

stack = []

# プッシュ
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)

# ポップ
stack.pop()
print(stack)
stack.pop()
print(stack)

[1, 2, 3]
[1, 2]
[1]

キュー

from collections import deque

# キューの定義
queue = deque(["A","B","C"])
print(queue)

# エンキュー
queue.append("D")
print(queue)

# デキュー
queue.popleft()
print(queue)

deque(['A', 'B', 'C'])
deque(['A', 'B', 'C', 'D'])
deque(['A', 'B', 'C'])

ヒープ(heap)

ヒープとは子要素は親要素より常に大きいか等しい(または常に小さいか等しい)
という制約を持つ木構造のデータの事です。

単にヒープと言う場合二分木を使った二分ヒープを指すことが多いです。

参考：wikipedia

ヒープはPythonではheapqライブラリで実現することができます。
ヒープでは最小値(もしくは最大値)を直ぐに取り出すことができます。

import heapq

# リストを作成
heap = [1, 6, 8, 0, -1]
print(heap)

# 既存のリストをヒープ化(最小値)
heapq.heapify(heap)
print(heap)

# 要素を追加
heapq.heappush(heap, 10)
print(heap)

# 最小値を削除
print(heapq.heappop(heap))
print(heap)

max_heap = [3,7,5,9,-2]
print(max_heap)
# 最大値でヒープ作成
heapq._heapify_max(max_heap) 
print(max_heap)

# 最大値を削除
print(heapq._heappop_max(max_heap))
print(max_heap)

[1, 6, 8, 0, -1]
[-1, 0, 8, 1, 6]
[-1, 0, 8, 1, 6, 10]
-1
[0, 1, 8, 10, 6]
[3, 7, 5, 9, -2]
[9, 7, 5, 3, -2]
9
[7, 3, 5, -2]

ソートアルゴリズムについて

ソートアルゴリズムは並び替えを行うアルゴリズムのことです。
単純に並び替えを行うにも様々なバリエーションがあります。

安定なstable並び替えとはデータ中に同一キーを持つレコードが複数ある場合
並べ替えた後に並べ替え前のレコードの順序関係が維持されます。

並べ替えることで並べ替え前の位置関係が崩れるような並べ替えを
不安定unstableな並べ替えといいます。

並べ替えが高速で終了し安定する並べ替えアルゴリズムの採用が望ましいです。

ソートアルゴリズムではその計算量なども1つの目安になります。
一般的に言われているソート アルゴリズムの計算量は以下の通りです。

アルゴリズム 安定性 平均時間 最悪時間 最良時間 最悪空間量
バブルソート 安定 $\mathcal{O}(n^2)$ $\mathcal{O}(n^2)$ $\mathcal{O}(n)$ $\mathcal{O}(1)$
選択ソート 不安定 $\mathcal{O}(n^2)$ $\mathcal{O}(n^2)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$
挿入ソート 安定 $\mathcal{O}(n^2)$ $\mathcal{O}(n^2)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$
ヒープソート 不安定 $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(1)$
マージソート 安定 $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n)$
クイックソート 不安定 $\mathcal{O}(n\log n)$ $\mathcal{O}(n^2)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$
pythonソート(Timソート) 安定 $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$

ここからは様々なソートアルゴリズムについて見ていきましょう。
実装例も載せていますが、もっと良い書き方があると思います。

バブルソート(bubble sort)

バブルソートはリストにおいて隣り合うふたつの要素の値を比較して
条件に応じた交換を行う整列アルゴリズムです。

値の大きい順(降順)か値の小さい順(昇順)にリストを並び替えます。

# バブルソート 
def bubble_sort(data):
    for i in range(len(data)):
        for j in range(len(data) - i - 1):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data

選択ソート(select sort)

選択ソートは配列の最小値(最大値)を持つ要素を探して
それを配列の先頭要素と交換することで整列を行うアルゴリズムです。

# 選択ソート
def select_sort(data):
    for i in range(len(data)):
        min = i
        for j in range(i + 1, len(data)):
            if data[min] > data[j]:
                min = j
        data[i], data[min] = data[min], data[i]
    return data

挿入ソート(insert sort)

挿入ソートはリストの整列済みの部分に対して新たな要素を適切な位置に挿入することで
整列を行うアルゴリズムです。

# 挿入ソート
def insert_sort(data):
    for i in range(1, len(data)):
        temp = data[i]
        j = i - 1
        while (j >= 0) and (data[j] > temp):
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = temp
    return data

ヒープソート(heap sort)

ヒープソートとはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムです。

未整列のリストから要素を取り出し、順にヒープに追加する。
すべての要素を追加するまで次の操作を繰り返す(ルートを取り出し整列済みリストに追加する)

# ヒープソート
def heap_sort(data):
    for i in range(len(data)):
        j = i
        while (j > 0) and (data[(j - 1) // 2] < data[j]):
            data[(j - 1) // 2], data[j] = data[j], data[(j - 1) // 2]
            j = (j - 1) // 2

    for i in range(len(data), 0, -1):
        data[i - 1], data[0] = data[0], data[i - 1]
        j = 0
        while ((2 * j + 1 < i - 1) and (data[j] < data[2 * j + 1]))\
            or ((2 * j + 2 < i - 1) and (data[j] < data[2 * j + 2])):
            if (2 * j + 2 == i - 1) or (data[2 * j + 1] > data[2 * j + 2]):
                data[j], data[2 * j + 1] = data[2 * j + 1], data[j]
                j = 2 * j + 1
            else:
                data[j], data[2 * j + 2] = data[2 * j + 2], data[j]
                j = 2 * j + 2
    return data

pythonではヒープキューを実現するライブラリheapqを用いて
簡易にヒープソート を書くこともできます。

import heapq

# heapqを用いたヒープソート 
def heap_sort2(data):
    h = data.copy()
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]

マージソート(merge sort)

マージソートは並べ替えたい配列を再帰的に分割していき、再び併合マージし
並び替えを実現しようとするソートアルゴリズムです。

# マージソート
def merge_sort(data):
    if len(data) <= 1:
        return data
    m = len(data) // 2
    l = merge_sort(data[:m])
    r = merge_sort(data[m:])
    return merge(l , r)

def merge(left, right):
    res , i , j = [], 0, 0
    while (i < len(left)) and (j < len(right)):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    if i < len(left):
        res.extend(left[i:])
    if j < len(right):
        res.extend(right[j:])
    return res

クイックソート(quick sort)

クイックソートはデータの比較と交換回数が非常に少ないのが特徴で
ランダムに散らばっているデータに対して、効率良く並べ替えを実現できますが
安定はしないアルゴリズムです。

def quick_sort(data):
    def quick(list, left, right):
        pl = left
        pr = right
        y = list[(pl + pr) // 2]
        while True:
            while list[pl] < y: pl += 1
            while list[pr] > y: pr -= 1
            if pl <= pr:
                list[pl], list[pr] = list[pr], list[pl]
                pl += 1
                pr -= 1
            if pl > pr:
                break
        if left < pr: quick(list, left, pr)
        if pl < right: quick(list, pl, right)
        return data
    quick(data, 0, len(data) - 1)
    return data

Pythonの標準ソート(sort)

Pythonの標準ソートは(恐らくは)Timsortです。

Timsortはマージソートと挿入ソートから派生したハイブリッドの安定した
ソートアルゴリズムでさまざまな種類のデータで適切に機能するように設計されています。

def python_sort(data):
    data.sort()
    return data

ソートアルゴリズムの実行時間比べ

上記のソートアルゴリズムの実行時間を測ってみましょう。
下記のようなコードで簡易に測ります。

10000個の数値の並び替えを行います。
jupyter notebookであれば%timeを用いると時間を測ることができます。

import numpy as np
import sys
sys.setrecursionlimit(20000)

data = np.arange(10000)
np.random.shuffle(data)
data = list(data)

print('bubble_sort')
%time l = bubble_sort(data)
print('select_sort')
%time l = select_sort(data)
print('insert_sort')
%time l = insert_sort(data)
print('heap_sort')
%time l = heap_sort(data)
print('heap_sort2')
%time l = heap_sort2(data)
print('merge_sort')
%time l = merge_sort(data)
print('quick_sort')
%time l = quick_sort(data)
print('python_sort')
%time l = python_sort(data)

bubble_sort
CPU times: user 18 µs, sys: 0 ns, total: 18 µs
Wall time: 20 µs
select_sort
CPU times: user 18 µs, sys: 1 µs, total: 19 µs
Wall time: 21 µs
insert_sort
CPU times: user 7 µs, sys: 0 ns, total: 7 µs
Wall time: 10 µs
heap_sort
CPU times: user 38 µs, sys: 1 µs, total: 39 µs
Wall time: 40.1 µs
heap_sort2
CPU times: user 11 µs, sys: 0 ns, total: 11 µs
Wall time: 12.9 µs
merge_sort
CPU times: user 31 µs, sys: 1e+03 ns, total: 32 µs
Wall time: 33.1 µs
quick_sort
CPU times: user 13 µs, sys: 1 µs, total: 14 µs
Wall time: 14.8 µs
python_sort
CPU times: user 4 µs, sys: 0 ns, total: 4 µs
Wall time: 6.2 µs

さて時間が一番短いのはPythonの標準ソートですね。

ここらへんは実装の仕方次第でもかなり変わると思いますが
標準ソートを超える速さを実現するのはかなり至難だと思いますので
通常はソートに関しては自前でプログラムを書く必要はないかと思います。

まとめ

Pythonのソートは非常に高性能なのであまり普段は気にしていないかもしれませんが
ソートで困ることは少ないです。

どういった仕組みでソートが行われているのか
それぞれの手法でどう違っているのかを見比べてみると
アルゴリズムの奥深さが分かってくると思います。

君がエンジニアになるまであと40日

作者の情報

乙pyのHP：
http://www.otupy.net/

Youtube：
https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw

Twitter：
https://twitter.com/otupython

3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?