整列アルゴリズム

in  

整列アルゴリズムについて

整列アルゴリズム

バブルソート

一番右から隣あう値を比較していきながら一番小さい値を左に移動してい来ます。左に到達した値はソート済として移動しません。次からソート済以外の列に関して同様の処理を行います。計算時間は \( \varTheta(n^2) \) になります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def bubble_sort(arr):

    for i in range(0, len(arr) - 1):

        for j in range(len(arr) - 1, i, -1):
            if arr[j] < arr[j - 1]:
                temp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = temp
    return arr

if __name__ == "__main__":
    a = [1, 3, 2, 4, 7, 6, 8, 5]
    print(bubble_sort(a))
[1, 2, 3, 4, 5, 6, 7, 8]

選択ソート

未ソートの中から一番小さい数を選び出して順に並べていくソートの方法です。計算時間は \( \varTheta(n^2) \) になります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def selection_sort(arr):

    for left in range(0, len(arr)):

        positionOfMin = left

        for location in range(left + 1, len(arr)):
            if arr[location] < arr[positionOfMin]:
                positionOfMin = location

        temp = arr[left]
        arr[left] = arr[positionOfMin]
        arr[positionOfMin] = temp
    return arr

a = [1, 3, 2, 4, 7, 6, 8, 5]
print(selection_sort(a))
[1, 2, 3, 4, 5, 6, 7, 8]

挿入ソート

選ばれた値を適切な場所に挿入していくアルゴリズムになります。計算時間は \( \varTheta(n^2) \) になります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def insert_sort(arr):
    for j in range(1, len(arr) ):

        temp = arr[j]
        i = j - 1
        while i >= 0 and arr[i] > temp:
            arr[i + 1] = arr[i]
            i = i - 1
        arr[i + 1] = temp
    return arr

a = [1, 3, 2, 4, 7, 6, 8, 5]
print(insert_sort(a))
[1, 2]

常に j より左側はソートされている状態を維持しながら、arr[j] より大きな値がなくなるまで値を右にずらしていきます。

分割統治法

分割統治法とは元の問題を小さなサイズの似た問題に分割して、それぞれを解いた後に結合する方法です。

  • 分割: 元の問題を小さなサイズに分割する
  • 統治: 分割した小さなサイズに対して解く
  • 結合: 解いた解を組み合わせる

クイックソート

クイックソートは分割統治法の考え方を取り入れたアルゴリズムです。分割のためにデータの中からpivotと呼ばれるものを選択し、その値を基準に分割しながらソートしていきます。 計算時間は \( \varTheta(n \log n) \) ですが入力によっては最悪の場合の計算時間は \( \varTheta(n^2) \) になります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def quick_sort(arr:list):
    return _quick_sort(arr, 0, len(arr) - 1)


def _quick_sort(arr:list, start:int, end:int):
    if not arr:
        return arr

    pivot = arr[int((end + start) / 2)]
    i = start
    j = end
    while True:
        while arr[i] < pivot:
            i += 1
        while pivot < arr[j]:
            j -= 1
        if i >= j:
            break
        tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        i += 1
        j -= 1
    if start < i - 1:
        _quick_sort(arr, start, i - 1)
    if j + 1 < end:
        _quick_sort(arr, j + 1, end)
    return arr

if __name__ == "__main__":
    print(quick_sort([1, 3, 2, 4, 7, 6, 8, 5]))
[1, 2, 3, 4, 5, 6, 7, 8]

マージソート

マージソートもクイックソート同様に分割統治法の考え方を取り入れたアルゴリズムです。配列を半分に分割して行ってソートした上で結合していきます。 計算時間は \( \varTheta(n \log n) \) になります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def merge_sort(arr) -> list:

    if len(arr) <= 1:
        return arr

    pivot = int(len(arr) / 2)
    return merge(merge_sort(arr[:pivot]), merge_sort(arr[pivot:]))


def merge(arr1, arr2) -> list:
    ret = list()
    len1 = len(arr1)
    len2 = len(arr2)

    i = j = 0
    arr1_val = arr1[i]
    arr2_val = arr2[j]

    while len(ret) < len1 + len2:

        if arr1_val < arr2_val:
            ret.append(arr1_val)
            if i < len1 - 1:
                i += 1
                arr1_val = arr1[i]
            else:
                arr1_val = float('inf')

        elif arr1_val >= arr2_val:
            ret.append(arr2_val)
            if j < len2 - 1:
                j += 1
                arr2_val = arr2[j]
            else:
                arr2_val = float('inf')
    return ret

if __name__ == '__main__':
    a = [1, 3, 2, 4, 7, 6, 8, 5]
    print(merge_sort(a))
[1, 2, 3, 4, 5, 6, 7, 8]
11111113233233332222244444445777766656678676885887555858

基数ソート

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def radix_sort(a):
    d = len(str(max(a)))
    for i in range(0, d):
        bucket = [[] for _ in range(10)]
        for e in a:
            v = (int(e % 10**(i + 1) / 10**i))
            bucket[v].append(e)

        j = 0
        for lis in bucket:
            for e in lis:
                a[j] = e
                j += 1

a = [250, 900, 123, 800, 143, 700, 600, 501]
radix_sort(a)
print(a)
[123, 143, 250, 501, 600, 700, 800, 900]

Share