開始→並べ替え

集計順に並べ替える

先生は学生をいちいち指さすのがおっくうで、学生たちが自分で並ぶ方法があるかどうか悩んでいる.10人の生徒を同時に並ばせるとうるさいかもしれないので、5人で2組に分けて、その中で身長順に並ばせてもらいます.
2|現在、先生の前には2行のボタンが順番に並んでいます(中間結果行).
3|先生は各行の一番前の2人の学生の中からもっと小さい民秀を抽出し、最後の結果行に置いた.その後、各中間結果行の前の2人の学生を比較し、より小さな学生を最終結果行の民秀の後ろに並べた.
この手順を繰り返すと、中間の結果行が消え、中間結果行のすべての人が最終結果行に配置されます.

簡単に説明するマージソートアルゴリズム

# 쉽게 설명한 병합 정렬
# 입력: 리스트 a
# 출력: 정렬된 새 리스트

 
def merge_sort(a):
    n = len(a)
    # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요 없음
    if n <= 1:
        return a
    # 그룹을 나누어 각각 병합 정렬을 호출하는 과정
    mid = n // 2              # 중간을 기준으로 두 그룹으로 나눔
    g1 = merge_sort(a[:mid])  # 재귀 호출로 첫 번째 그룹을 정렬
    g2 = merge_sort(a[mid:])  # 재귀 호출로 두 번째 그룹을 정렬
    # 두 그룹을 하나로 병합
    result = []               # 두 그룹을 합쳐 만들 최종 결과
    while g1 and g2:          # 두 그룹에 모두 자료가 남아 있는 동안 반복
        if g1[0] < g2[0]:     # 두 그룹의 맨 앞 자료 값을 비교
            # g1 값이 더 작으면 그 값을 빼내어 결과로 추가
            result.append(g1.pop(0))
        else:
            # g2 값이 더 작으면 그 값을 빼내어 결과로 추가
            result.append(g2.pop(0))
    # 아직 남아 있는 자료들을 결과에 추가
    # g1과 g2 중 이미 빈 것은 while을 바로 지나감
    while g1:
        result.append(g1.pop(0))
    while g2:
        result.append(g2.pop(0))
    return result

 
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5] 	
print(merge_sort(d))

運転結果

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

集計ソート関数の最初の部分が終了条件です.

n = len(a)

if n <= 1:

    return a

指定されたリストaのサイズが1未満である場合(すなわち、1つまたはすべてが空である場合)、ソートする必要がないので、入力リストに戻って再帰呼び出しを終了する.
以下は、リスト全体を半分に分割し、各再帰呼び出しにマージする部分です.

mid = n // 2             # 두 그룹으로 나누기 위한 중간 값

g1 = merge_sort(a[:mid]) # 재귀 호출로 첫 번째 그룹을 정렬

g2 = merge_sort(a[mid:]) # 재귀 호출로 두 번째 그룹을 정렬

リストのデータが奇数の場合、半分に分割する方法

n/2はリスト長nを2で割った部分であり、nが5に等しい場合、n/2は2である.データを2つのグループと3つのグループに分けます.
また、a[:mid]は、リストaの0番の位置からリストaの中間位置まで材料をコピーする文章であることに注意してください.
また、a[mid:]は、リストaのmid位置からリストの末尾にコピーした材料から新しいリストを作成する文章である.

Ex

>>> a = [1, 2, 3, 4, 5]
>>> mid = len(a) // 2
>>> mid
2
>>> a[:mid]
[1, 2]
>>> a[mid:]
[3, 4, 5]

連結ソート・ステップの分析

①10個の数字を2つのグループ(g 1、g 2)に分けます.

g1: [6 8 3 9 10]
g2: [1 2 4 7 5]

②2つのグループをそれぞれ並べ替える(再帰呼び出し部分であるため、この部分は後述するが、まず各グループを並べ替える).

g1: [3 6 8 9 10]
g2: [1 2 4 5 7]

③2つのグループを結合し、1つのグループに再結合します.
2つのグループの最初の値を比較し、小さい値を減算して結果リストに入れます.g 1の最初の値は3であり、g 2の最初の値は1であるため、1を減算して結果リスト(result)に入れる.

g2: [2 4 5 7]
result: [1]

④2つのグループの最初の値を比較し、小さい値を取って結果リストに入れます.今回,g 2中の2を抽出して並べ替えた.

g1: [3 6 8 9 10]
g2: [4 5 7]
result: [1 2]

⑤今回はG 1の3を選んでソートします.

g1: [6 8 9 10]
g2: [4 5 7]
result: [1 2 3]

この手順を繰り返すと、データのセットがすべて失われ、空になります.

g1: [8 9 10]
g2: []
result: [1 2 3 4 5 6 7]

üg 2にはデータがないので、比較する必要はありません.g 1の残りの値をすべて結果に移動すれば、ソートは終了します.

g1: []
g2: []
result: [1 2 3 4 5 6 7 8 9 10]

連結ソートで再帰を呼び出す

集計ソートでは、②番プロセスから2つのグループに分かれた資料をそれぞれソートします.では、分割されたグループはどのようなソートアルゴリズムでソートされますか?
連結ソートです.つまり、マージソートを行う過程で、分割されたリストを2回マージソートし直す.
これは,円盤がnのハノイの塔問題,円盤がn−1のハノイの塔問題を理解するために再呼び出されるのと同様である.
再帰呼び出しの3つの要件をもう一度思い出すと
1 . 関数で自分を再呼び出します.
2 . 再帰呼び出し時には、パラメータとしての入力が小さくなります.
3 . いくつかの終了条件が満たされている場合は、再帰呼び出しを終了します.
集計ソートは、10個のデータをソートするために、データを5つのグループに分けて集計ソート関数を呼び出します.すなわち,条件1,2は容易に確認できる.
では、終了条件は、集計ソートの入力リストに1つのデータしかないか、いっそデータがない場合はソートする必要がないので、入力リストに戻るだけで再帰呼び出しを終了することができます.

一般的な連結ソートアルゴリズム

ソート原理は同じですが、値は返されません.違いは、入力リストの資料の順序を直接変更することです.

# 병합 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)

def merge_sort(a):
    n = len(a)
    # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음
    if n <= 1:
        return
    # 그룹을 나누어 각각 병합 정렬을 호출하는 과정
    mid = n // 2    # 중간을 기준으로 두 그룹으로 나눔
    g1 = a[:mid]
    g2 = a[mid:]
    merge_sort(g1)  # 재귀 호출로 첫 번째 그룹을 정렬
    merge_sort(g2)  # 재귀 호출로 두 번째 그룹을 정렬
    # 두 그룹을 하나로 병합
    i1 = 0
    i2 = 0
    ia = 0
    while i1 < len(g1) and i2 < len(g2):
        if g1[i1] < g2[i2]:
            a[ia] = g1[i1]
            i1 += 1
            ia += 1
        else:
            a[ia] = g2[i2]
            i2 += 1
            ia += 1 
    # 아직 남아 있는 자료들을 결과에 추가
    while i1 < len(g1):
        a[ia] = g1[i1]
        i1+= 1
        ia += 1
    while i2 < len(g2):
        a[ia] = g2[i2]
        i2 += 1
        ia += 1

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
merge_sort(d)
print(d)

運転結果

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

例

アルゴリズム解析

集計ソートは、指定された問題を半分に分割し、それぞれ再帰的に呼び出す方法です.
このような大きな問題を小さな問題(分割)に分けて解く(征服)方法をアルゴリズム設計手法では「分割征服」と呼ぶ.
入力サイズが大きすぎて解けにくい問題を繰り返し細分化すると、非常に容易な問題(終了条件)となります.分割征服を十分に利用することは,計算の複雑さがより低い効率的なアルゴリズムの生成に役立つ.
分割征服による集計ソートの計算複雑度はO(n・logn)であり,選択ソートまたは挿入ソートの計算複雑度O(n二乗)より低かった.したがって、ソートが必要なデータが多いほど、ソートを選択したり挿入したりするよりも、ソートをマージする方がソート速度が速くなります.
例えば、大韓民国の5千万人の国民を生年月日順に並べて、n=50000000と入力した場合、n平方は2500兆、n・lognは約13億となる.2500兆は13億より200万倍も大きい数字だ.この事実を知れば,O(n 2)ソートアルゴリズムとO(n・logn)ソートアルゴリズムの計算時間の差がどれほど大きいか推測できる.

降順ソート

昇順ソートでは、比較値部分(g 1[i 1]# 내림차순 병합 정렬 # 입력: 리스트 a # 출력: 없음(입력으로 주어진 a가 정렬됨) def merge_sort(a): n = len(a) # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음 if n <= 1: return # 그룹을 나누어 각각 병합 정렬을 호출하는 과정 mid = n // 2 g1 = a[:mid] g2 = a[mid:] merge_sort(g1) merge_sort(g2) # 두 그룹을 합치는 과정(병합) i1 = 0 i2 = 0 ia = 0 while i1 < len(g1) and i2 < len(g2): if g1[i1] > g2[i2]: # 부등호 방향 뒤집기 a[ia] = g1[i1] i1 += 1 ia += 1 else: a[ia] = g2[i2] i2 += 1 ia += 1 while i1 < len(g1): a[ia] = g1[i1] i1 += 1 ia += 1 while i2 < len(g2): a[ia] = g2[i2] i2 += 1 ia += 1 d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5] merge_sort(d) print(d)