Algorithm 공부 #07 - 정렬(병합 정렬과 기수 정렬)

 

Algorithm 공부 #07 - 정렬(병합 정렬과 기수 정렬)

 

병합 정렬(Merge Sort)

    ● 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘

    ● 시간 복잡도는 O(nlogn)

 

 

백준 2751번 수 정렬하기2

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

※ N의 최대 범위가 1,000,0000이므로 O(nlogn)의 병합 정렬을 사용해서 문제 풀기 ※

● 병합 정렬 함수 슈도 코드

     병합 정렬(start,end){

          start = 시작점 / middle=중간점 / end = 종료점 

          sort(start,middle)

          sort(middle+1, end)

 

          for(start~end){

               temp배열에 A배열값 저장

             }

       }

      

        // 두 그룹을 병합하는 로직 

        index1 -> 앞쪽 그룹 시작점

        index2 -> 뒤쪽 그룹 시작점

 

        while(index1<=middle && index2<=end){

                  양쪽 그룹의 인덱스값을 비교하여 더 작은 값을 배열에 순차적으로 저장

                  선택된 데이터의 인덱스는 한 칸씩 옆으로 이동

                  이후 남은 데이터들은 배열에 저장

          }

 

#include<iostream>
#include<vector>
using namespace std;

static vector<int>A;  // 입력받는 배열
static vector<int>temp; //임시 배열
void merge_sort(int start, int end);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	A = vector<int>(N + 1, 0);
	temp = vector<int>(N + 1, 0);

	for (int i = 1; i <= N; i++)
		cin >> A[i];
	
	merge_sort(1, N); // 정렬 시작
	 
	for (int i = 1; i <= N; i++)
		cout << A[i] << '\n';
}

void merge_sort(int start, int end) {
	if (end - start < 1)
		return;

	int middle = start + (end - start) / 2; // 중간점 설정

	merge_sort(start, middle); //앞쪽 그룹 
	merge_sort(middle + 1, end); // 뒤쪽 그룹

	for (int i = start; i <= end; i++)
		temp[i] = A[i]; // 임시로 값 저장

	int k = start;
	int index1 = start; // 앞쪽 그룹 시작점
	int index2 = middle + 1; // 뒤쪽 그룹 시작점

	while (index1 <= middle && index2 <= end) {
		if (temp[index1] > temp[index2]) {
			A[k] = temp[index2];
			index2++;
			k++;
		}
		else {
			A[k] = temp[index1];
			index1++;
			k++;
		}
	}

	while (index1 <= middle) { // 다 안채워진 데이터 삽입
		A[k] = temp[index1];
		k++;
		index1++;
	}
	while (index2 <= end) {   // 다 안채워진 데이터 삽입
		A[k] = temp[index2];
		index2++;
		k++;
	}
}

 

 

 

백준 1517번 버블 소트

https://www.acmicpc.net/problem/1517

1517번: 버블 소트

 

※ 제목은 버블 정렬이지만 버블 정렬로 풀면 N<=500,000 이므로 시간 복잡도를 초과함 ※ 

● 시간 복잡도가 O(nlogn)인 병합 정렬로 접근하기

● 기본적인 병합 정렬과 비슷하나 중간에 swap해주는 개수를 count해줘서 result로 출력해야함

● 그룹들을 병합할 때 앞 그룹과 뒤 그룹의 데이터 값을 비교하면서 배열의 인덱스를 채워주는데,

   여기서 뒤 그룹의 데이터가 더 작아서 배열의 앞쪽에 채우게 되는 경우에는 swap이 발생한다고 생각하면 됨

 

#include<iostream>
#include<vector>
using namespace std;

static vector<int>A;
vector<int>temp;
void merge_sort(int start, int end);
static long result;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	A = vector<int>(N + 1, 0);
	temp = vector<int>(N + 1, 0);

	for (int i = 1; i <= N; i++)
		cin >> A[i];
	result = 0;
	merge_sort(1, N);
	cout << result;
}
void merge_sort(int start, int end) {

	if (end - start < 1)
		return;

	int middle = start + (end - start) / 2;

	merge_sort(start, middle);
	merge_sort(middle + 1, end);

	for (int i = start; i <= end; i++)
		temp[i] = A[i];

	int index1 = start;
	int k = start;
	int index2 = middle+1;

	while (index1 <= middle && index2 <= end) {
		if (temp[index1] > temp[index2]) {
			A[k] = temp[index2];
			result = result + index2 - k; // 뒤쪽 그룹의 데이터가 앞으로 가는 경우는
			index2++;             // swap이 발생한다고 생각하고 index2와 k의 차이의 인덱스만큼 이동 
			k++;                // 즉, index2-k만큼의 swsap이 발생
		} 
		else {
			A[k] = temp[index1];
			index1++;
			k++;
		}
	}

	while (index1 <= middle) {
		A[k] = temp[index1];
		k++;
		index1++;
	}
	while (index2 <= end) {
		A[k] = temp[index2];
		k++;
		index2++;
	}
}

 

기수 정렬(Merge Sort)

    ● 값을 비교하지 않는 정렬

    ● 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교

    ● 시간 복잡도는 O(kn), k는 데이터의 자릿수, 시간복잡도가 가장 짧은 정렬

 

 

백준 10989번 수 정렬하기3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

#include<iostream>
#include<vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;
	vector<int>A(N, 0);
	vector<int>ct(10001, 0);
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		ct[A[i]]++;  // ct배열에 현재 수에 해당하는 인덱스 ++
	}
	
	for (int i = 0; i < 10001; i++) {
		if (ct[i] != 0) {
			for (int j = 0; j < ct[i]; j++) // ct[i]에 있는 개수만큼 출력
				cout << i << '\n';
		}
	}

}