分割征服

分割征服とは、大きな問題を細分化して解決する方法である.top-down方式で分解して解決できる再帰的な概念が含まれていますが、bottom-up方式で繰り返し文で実現することもできます.
また、問題を分割する際に既存のデータをすべて巡回する必要があるという問題を低減することができ、時間的複雑さを低減することができる.
この特性を用いて実現したソートアルゴリズムはquick sortとmerge sortである.

連結ソート

連結ソートは、名前に従って分割および連結を行い、並べ替えを完了するアルゴリズムです.

図に示すように、分割してからソートに戻ります.
O(n^2)よりも速いのは,マージソートを行うと,すべての要素の後ろに大きな要素しかなく,2回の遍歴を必要としないことを決定できるからである.
一時的な配列(2つのセグメント配列を格納)が必要であるため,O(n)空間の複雑さを占有する.
しかし,これは安定したO(nlogn)時間の複雑さを保証することができ,従ってよく用いられるソート方式である.
最悪、最良、平均的にO(nlogn)のソート時間を保証する.

def merge_sort(x, low, high, arr):
    if low >= high:  # 길이가 1이라면 혹은 길이가 0일수도있음
        return

    mid = (low + high )// 2 # 미드를 결정해 주는 부분

    merge_sort(x, low, mid, arr) # 분할하는 부분(앞)
    merge_sort(x, mid + 1, high, arr) # 분할하는 부분(뒤)

    # 합쳐주는 방법
    i, j = low, mid + 1
    # low, mid+1 은 합병하는 내용인데 index 를 벗어나버릴 수도 있음 이걸 처리해줘야함
    for k in range(low, high + 1):
    	# 현재까지 분할 된 배열을 모두 순회 for문 한번으로 정렬이 가능
        if i > mid: # 왼쪽 배열은 mid 까지만 순회해야함. 그 이상가면 정렬할 배열을 초과
            # 배열을 초과할 경우 그 반대쪽 배열이 남아있다는 뜻이므로 그대로 임시 배열에 모두 붙여줌
            arr[k] = x[j]
            j += 1
        elif j > high: # 오른쪽 배열은 반대로 생각
            arr[k] = x[i]
            i += 1
        elif i <= mid and j <= high: # 만약 두 index가 모두 범위 안쪽이라면
            if x[i] > x[j]: # 왼쪽에 더 큰 수가 있으면 오른쪽 수를 임시배열에 붙임
                arr[k] = x[j]
                j += 1 
            else: # 오른쪽에 더 큰 수가 있으면 왼쪽배열의 수를 임시배열에 붙임
                arr[k] = x[i]
                i += 1
           # 이런 나이브한 구현이 가능한 이유는 분할 후 정복하면서 계속 정렬을 마치기 때문에, 
           # low ~ mid 사이의 배열과, mid ~ high 의 배열 사이에서는 정렬이 
           # 되어있다고(앞보다 뒤가 더 크다고) 보장할 수 있기 때문이다.
           
          
    x[low:high + 1] = arr[low:high + 1]
    # 해당 정렬된 배열을 x에 동기화 해주어야 한다. 
    return arr

クイックソート(Quick sort)

Quick Sortは分割征服においてMuji Sortと大差はないが,基準を定める方法で異なる.まず、メルギソットは半分に分けて実装する必要がありますが、クイックソットはpivotを指定し、その値に基づいてソートします.したがって、エラーのピボット(すべてのピボットが最大値または最小値の場合)が選択されている場合、たとえばソートされた配列で、最後の値をピボットとして指定した場合、O(n^2)が表示されます.
現実のデータはある程度並べ替えられており,ノイズ発生データが多いため,高速並べ替えアルゴリズムの性能がO(n^2)の並べ替えアルゴリズムに及ばない場合がある.
空間的複雑さはO(logn)であるが,より簡単に実現できる高速スイートは,新しい一時配列を作成して値を格納する方法によって実現される.
逆に、空間複雑度O(1)の実現は、所与のアレイ内で交換することによって実現されるため、メモリが節約されるが、実現はより複雑である.

時間の複雑さ

最悪:O(n^2)

最適:O(nlogn)

平均

:O(nlogn)

実装空間複雑度O(logn)

def quick_sort(x):
    pivot = len(x)-1 # 피벗은 분할 배열의 마지막 원소로
    if len(x) == 0: # 분할한 배열이 0이라면 리턴
        return []
    arr1, arr2 = [], [
    
    for i in range(len(x)-1): # 배열 순회하면서
        if x[i] > x[pivot]: # 피벗보다 큰 원소는 
            arr2.append(x[i]) # 임시배열 arr2에 넣고
        else:
            arr1.append(x[i]) # 피벗보다 작거나 작은 원소

    return quick_sort(arr1) + [x[pivot]] + quick_sort(arr2)
print(quick_sort([3, 5, 321, 3, 6, 23, 1, 223]))

実施空間複雑度O(1)

高速スイートは、その場でアルゴリズムで実現できます.省スペースで複雑度が良いのですが、実は実現が複雑です.

def quick_sort(x, start, end):
    if start >= end:
        return

    pivot = (start + end) // 2
    first_start = start
    first_end = end
    while start <= end:
        while x[start] < x[pivot]:  # 왼쪽 값 -> 더 큰 값있을경우 스왑
            start += 1

        while x[end] > x[pivot]:  # 오른쪽 값 -> 더 작은 값 스왑
            end -= 1

        if start <= end:
            x[start], x[end] = x[end], x[start]
            start += 1
            end -= 1

    quick_sort(x, first_start, start - 1)
    quick_sort(x, start, first_end)
    return x

チームワークアルゴリズム

これは多くの実際の言語に適用されるアルゴリズムです.
Java se 7、android、chrome v 8 JavaScriptエンジン、swift、rust、pythonなどの言語に適用されます...ほとんど言語占有率で測定され,ほとんどすべてのプログラミングに適したアルゴリズムと言える.
発生原理はInsersion sortとMerge sortを組み合わせたソート方式である.
小さい領域では、Insertionsortを実行し、sort最適化をマージします.

空間複雑度:O(n)

時間の複雑さ

最悪:O(nlogn)

最適:O(n)

平均

:O(nlogn)