[アルゴリズム]集計ソート-集計Sort(Python)
6349 ワード
📌 連結ソート
マージソートは分割征服技術と再帰アルゴリズムを用いたソートアルゴリズムである
与えられた配列の要素を残りの1つに分割し、並べ替えて元のサイズの配列にマージします.
静的ソートですが、小さな単位で区切られたソートを格納するために余分なスペースが使用されるため、位置ソートはありません.ただし、インデックスアクセスによる入力配列の更新により、メモリの使用を大幅に削減できます.(In-place Sort)
--
分割征服
与えられた問題を分割できない部分に分けてから統合し,元の問題の解答を得るアルゴリズム.一般に,提供されるものがよいほど,Conquerプロセスは容易であるため,分割プロセスが重要である.
アイデア
1. 주어진 배열을 더 이상 쪼갤 수 없을 때까지 둘로 분할한다.
2. 나뉜 두 개의 배열을 하나로 합치는데, 이 때, 크기가 작은 값이 앞에 오도록 한다.
3. 배열의 크기가 기존과 같아질 때까지 병합 과정을 반복한다.複雑度分析
O(N)である.O(logN)の時間がかかる.また,配列を結合する過程で配列内のすべての要素を比較する必要があるため,O(N)時間が必要である.したがって、集計ソートの時間的複雑さはO(NlogN)である.特長
👍 長所
👎 短所
インプリメンテーション
def merge_sort(arr, first, last):
if first >= last:
return
merge_sort(arr, first, (first+last)//2)
merge_sort(arr, (first+last)//2+1, last)
return sorting(arr, first, last)
def sorting(arr, first, last):
mid = (first + last) // 2
i, j = first, mid+1
temp = []
while i <= mid and j <= last:
if arr[i] <= arr[j]:
temp.append(arr[i])
i += 1
else:
temp.append(arr[j])
j += 1
while i <= mid:
temp.append(arr[i])
i += 1
while j <= last:
temp.append(arr[j])
j += 1
for k in range(first, last+1):
arr[k] = temp[k-first]
return arrコメントサイト
🙇🏻♂️ https://www.daleseo.com/sort-merge/
Reference
この問題について([アルゴリズム]集計ソート-集計Sort(Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@seongmini/Algorithm-병합-정렬-Merge-Sort-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol