[アルゴリズム]集計ソート-集計Sort(Python)

📌 連結ソート

マージソートは分割征服技術と再帰アルゴリズムを用いたソートアルゴリズムである
与えられた配列の要素を残りの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/