Divide and Conquer) Merge Sort

C++코드

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
vi v;
void mergeSort(int le, int ri) {
	if (le == ri - 1) {
		return;
	}
	int mid = (le + ri) / 2;
	mergeSort(le, mid);
	mergeSort(mid, ri);
	int l = le, r = mid;
	vi temp;
	while (1) {
		if (l == mid && r == ri)break;
		else if (r == ri) {
			temp.push_back(v[l++]);
		}
		else if (l == mid) {
			temp.push_back(v[r++]);
		}
		else {
			if (v[l] < v[r]) {
				temp.push_back(v[l++]);
			}
			else {
				temp.push_back(v[r++]);
			}
		}
	}
	int idx = 0;
	for (auto r : temp) {
		v[le + idx] = r;
		idx++;
	}
}
int main() {
	FAST;
	int n;
	cin >> n;
	int x;
	rep(i, n) {
		cin >> x;
		v.push_back(x);
	}
	mergeSort(0, v.size());
	for (int r : v) {
		cout << r << " ";
	}
}

 

 

java 코드

//main.java
package Devide_And_Conquer;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static List<Integer> v = new ArrayList<>();
	public static void main(String args[]) {
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		while(sc.hasNext()) {
			v.add(sc.nextInt());
		}
		sc.close();
		MergeSort ms=new MergeSort(v);
		ms.Sort(0, n);
		for(var d:v) {
			System.out.println(d);
		}
	}
}

 

//MergeSort.java
package Devide_And_Conquer;

import java.util.ArrayList;
import java.util.List;

public class MergeSort {
	List<Integer>lst;
	MergeSort(List<Integer>v){
		lst=v;
	}
	public void Sort(int le,int ri) {
		if(le==ri-1)return;
		int mid=(le+ri)/2;
		Sort(le,mid);
		Sort(mid,ri);
		int l=le,r=mid;
		List<Integer>temp=new ArrayList<>();
		while(true) {
			if(l==mid && r==ri)break;
			else if(l==mid)temp.add(lst.get(r++));
			else if(r==ri)temp.add(lst.get(l++));
			else {
				if(lst.get(l)<lst.get(r)) {
					temp.add(lst.get(l++));
				}
				else {
					temp.add(lst.get(r++));
				}
			}
		}
		int idx=0;
		for(var t:temp) {
			lst.set(le+(idx++), t);
		}
	}
}

 

 

 

분할정복 > 합병정렬

합병정렬(Merge Sort)알고리즘입니다.

분할정렬의 방법입니다.

 

시간복잡도는 Divide 과정에서 절반에 절반에 절반에..... 이므로 O(log(N))입니다.

그리고 COMBINE 과정에서 O(N)으로 정렬하므로

총 NlogN입니다.