入門-クイックソート

その前に、学生を2つのグループに分けて並べ替え、並べ替え後の2つのグループの学生のキーを再比較し、1行に統合します.
今回学習するクイックソート(Quicksort)は,マージソートと同じであるが,グループ化時のリード条件が異なる.すなわち,まずグループを条件と比較し,次いでそれぞれ再帰呼び出しを行い,マージする.

クイックキュー

先生は学生をいちいち指さすのがおっくうで、学生たちが自分で並ぶ方法があるかどうか悩んでいる.でも、10名の学生を一度に並ばせるとうるさいかもしれないのでグループ分けしたいです.
2|10人の中から1人を選んで基準にします.基準で選ばれたテホは真ん中に並んで、テホより背の低い学生をテホの前に立たせ、テホより背の高い学生をテホの後ろに立たせた(学生たちはテホと身長を比較すればいい).
3|標準のテホはじっと立っていて、テホより低い学生は小学生の間に立っていて、大学生は大学生の間に立っていて、身長順に並んでいて、並んで終わりました.

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

Pivotで左右に分ける

# 쉽게 설명한 퀵 정렬
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
 
def quick_sort(a):
    n = len(a)
    # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음
    if n <= 1:
        return a
    # 기준 값을 정하고 기준에 맞춰 그룹을 나누는 과정
    pivot = a[-1]  # 편의상 리스트의 마지막 값을 기준 값으로 정함
    g1 = []        # 그룹 1: 기준 값보다 작은 값을 담을 리스트
    g2 = []        # 그룹 2: 기준 값보다 큰 값을 담을 리스트
    for i in range(0, n - 1):  # 마지막 값은 기준 값이므로 제외
        if a[i] < pivot:       # 기준 값과 비교
            g1.append(a[i])    # 작으면 g1에 추가
        else:
            g2.append(a[i])    # 크면 g2에 추가
    # 각 그룹에 대해 재귀 호출로 퀵 정렬을 한 후
    # 기준 값과 합쳐 하나의 리스트로 결괏값 반환
    return quick_sort(g1) + [pivot] + quick_sort(g2)
 
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(quick_sort(d))

運転結果

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

高速ソートリスト[6,8,3,9,10,1,2,4,7,5]のプロセス

①リストに基準値を指定します.本書では、リストの最後の値をソートしやすい値として定義します.

[6 8 3 9 10 1 2 4 7 5]의 기준 값: 5

②g 1を標準値より小さい値を格納するリストとし、g 2を大きい値を格納するリストとする.
③リストの資料を標準値5と比較し、5未満の値をg 1、5より大きい値をg 2とする.例えば、6は5より大きいのでg 2に配置され、g 2および3は5より小さいのでg 1に配置される.

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

④再帰呼び出しによりg 1をソートする.関数でクイックソートを再呼び出すと、問題を解いて結果が返される[1234].
⑤再帰呼び出しによりg 2をソートする.同様に、クイックソートは問題を解決し、結果[678.9-10]を返します.
⑥現在、g 1には「標準より小さい値」が並べ替えられ、g 2には「標準より大きい値」が並べ替えられている.したがって、g 1、基準値、g 2の順に貼り付けると並べ替えが完了する.

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

ㅇ最終結果:[1 2 3 4 5 6 7 8 9 10]

と知る

クイックソート関数quick sort()は再帰呼び出し関数であるため、マージソートと同様に第1部で終了条件を指定します.
まず、所与のリストaのサイズが1未満である場合、すなわち、1つのデータしかない場合、または単に空である場合、ソートする必要がないため、入力リストに戻って再帰呼び出しを終了することができる.

n = len(a)
if n <= 1:
    return a

高速ソートには、グループ化するために基準値(pivot)も必要です.プログラムは、指定されたリストの最後の値を基準値として使用します.

pivot = a[-1]

次の文は、標準値とg 2クイックソート結果をg 1クイックソート結果に接続し、新しいリストを生成して返される文です.

return quick_sort(g1) + [pivot] + quick_sort(g2)

クイックソートの一般化

高速ソートの実際のインプリメンテーション(パーティション)は、新しいメモリを割り当てることなく、毎回交換値(swap)を使用してインプリメンテーションされます.

一般的な高速ソートアルゴリズム

簡単に説明するクイックソートプログラムは、新しいリストg 1およびg 2を作成し、値を分類し、新しい結果リストを作成および返します.次に、入力リストで直接再配置する通常のクイックソートを見てみましょう.

# 퀵 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
# 리스트 a에서 어디부터(start) 어디까지(end)가 정렬 대상인지
# 범위를 지정하여 정렬하는 재귀 호출 함수
def quick_sort_sub(a, start, end):
    # 종료 조건: 정렬 대상이 한 개 이하이면 정렬할 필요가 없음
    if end - start <= 0:
        return
    # 기준 값을 정하고 기준 값에 맞춰 리스트 안에서 각 자료의 위치를 맞춤
    # [기준 값보다 작은 값들, 기준 값, 기준 값보다 큰 값들]
    pivot = a[end]   # 편의상 리스트의 마지막 값을 기준 값으로 정함
    i = start
    for j in range(start, end):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[end] = a[end], a[i]
    # 재귀 호출 부분
    quick_sort_sub(a, start, i - 1) # 기준 값보다 작은 그룹을 재귀 호출로 다시 정렬
    quick_sort_sub(a, i + 1, end)  # 기준 값보다 큰 그룹을 재귀 호출로 다시 정렬
 
# 리스트 전체(0 ~ len(a) -1)를 대상으로 재귀 호출 함수 호출
def quick_sort(a):
    quick_sort_sub(a, 0, len(a) - 1)
 
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort(d)
print(d)

運転結果

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

基準値の重要性

並んでいる間に先生が決めた基準が10人の中で一番背の小さい学生だったらどうなりますか?残念なことに、標準より小さいグループ(g 1)には学生は一人もおらず、標準より大きいグループ(g 2)には他の学生が集まっている.これにより、グループ化の意味がなくなり、迅速なソートの効率が低下します.
したがって、クイックソートでは、「良い基準」を決定することがソート効率を測定する重要な基準です.しかしながら、標準を特定する方法は難しいため、サンプルプログラムは、資料の最後の値を標準値として簡単に使用する.

アルゴリズム解析

高速ソートの計算複雑度は、最悪の場合はO(n)平方、例えばソートの選択や挿入ソートであるが、平均的な場合はO(n・logn)、例えばマージソートである.
最悪の場合、この基準は正しくなく、正しくグループ化できません.しかし,幸いなことに,良い基準値を決定するアルゴリズムについては多くの研究がなされているため,高速ソートは多くの場合O(n・logn)のソートを完了することができる.