본문 바로가기
Java/Java 알고리즘

[알고리즘] 1-5. 병합 정렬 [재귀 함수, 투 포인터 이용]

앤 썸 2022. 6. 28. 22:15
반응형

1. 병합 정렬

: 분할 정복 [divide and conquer] 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하면서 합치는 알고리즘

-> 시간 복잡도의 평균값은 O(nlogn)으로 준수한 편이다.

 

(1) 구현 과정

-> 가장 작은 데이터 집합으로 분할 후, [divide]

-> 병합해 가면서 정렬 [conquer]

-> 각각의 집합을 정렬 후 -> 병합 -> 정렬 후 -> 병합 과정을 반복해 전체를 오름차순으로 정렬

: 2개의 그룹을 병합하는 원리를 이용

 

# 2개의 그룹을 병합하는 과정 [투 포인터 개념 이용]

  1. 왼쪽 포인터와 오른쪽 포인터의 값을 비교
  2. 두 포인터가 가리키는 값 중 작은 값을 결과 배열에 추가하고, 해당 포인터를 오른쪽으로 1칸 이동 [우측 시프트 연산]
  3. 두 포인터 모두 마지막 index를 가리킬 경우 종료

 

문제 20. 

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

 

입력
첫 번째 줄에 수의 개수 N(1 <= N <= 1,000,000), 두 번째 줄부터 N개의 줄에 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이며,  수는 중복되지 않는다.


출력
1 번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1 줄에 1 개씩 출력한다.

 

예제 입력

5 //수의 개수
5
4
3
2
1

 

예제 출력

1
2
3
4
5

1단계. 문제 분석하기

-> N의 범위를 보고, O(nlogn)의 시간 복잡도를 이용해 정렬 수행

 

2단계. 손으로 풀어 보기

  1. 정렬할 그룹을 최소 길이로 분리한다.
    1. 배열의 길이가 5이므로 2, 2, 1로 나눈다.
    2. 나눈 그룹별로 병합 정렬을 수행한다.
    3. 그룹별 index1, index2를 지정해 비교하면서 결과배열에 추가한다.
    4. 그룹이 3개이므로, 2번째, 3번째 그룹을 병합
  2. 이어서 병합된 그룹을 대상으로 재정렬한다.
    1. 병합한 그룹끼리, 정렬을 수행
    2. 그룹별 index를 비교해 정렬
  3. 다시 병합 후 정렬

3단계. 슈도코드 작성하기

N（정렬할 수 개수）
A（정렬할 배열 선언하기）
tmp（정렬할 때 잠시 사용할 임시 배열 선언하기）
for（N의 개수만큼）
{
A 배열 선언하기
}
병합 정렬 함수 수행하기
결괏값 출력하기
// 병합 정렬 수행하기
병합 정렬（s, e） {
나시작점）, e（종료점）, m（중간점）
// 재귀 함수 형태로 구현하기
병합 정렬（s、m）
병합 정렬（m + 1, e）
for（s ~ e）
{
tmp 배열 저장하기
}
// 두 그룹을 병합하는 로직
indexl - 앞쪽 그룹 시작점
index2 — 뒤쪽 그룹 시작점
while（index1 <= 중간점 && index2 <= 종료점）
양쪽 그룹의 index가 가리키는 값을 비교한 후 더 작은 수를 선택해 배열에 저장하고,
선택된 데이터의 index 값을 오른쪽으로 한 칸 이동하기
반복문의 끝난 후 남아 있는 데이터 정리하기
}
package sorting.ch04;

import java.util.Scanner;

public class sorting_q20 {

	// 매번 파라미터로 보내지않고, static으로 선언
	public static int[] arr, tmp;

	public static void main(String[] args) {
		sorting_q20 T = new sorting_q20();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		arr = new int[n + 1];
		tmp = new int[n + 1];
		for (int i = 1; i <= n; i++)
			arr[i] = kb.nextInt();

		T.sort(1, n);
		for (int i = 1; i <= n; i++)
			System.out.println(arr[i]);

	}

	private void sort(int start, int end) {
		// 최소 길이로 분할 -> 처음부터 중간점까지 집합 1, 중간점+1부터 마지막까지 집합2
		// -> 각각 정렬하는 로직
		if (end - start < 1) return;
		int mid = start + (end - start) / 2;

		sort(start, mid);
		sort(mid + 1, end);

		for (int i = start; i <= end; i++) tmp[i] = arr[i];

		// 두 그룹을 병합하는 로직
		// -> 양쪽 그룹의 index가 가리키는 값을 비교해 더 작은 수를 선택해 배열에 저장하고,
		// 선택된 데이터의 index 값을 오른쪽으로 한 칸 이동하기
		int k = start;
		int p1 = start;
		int p2 = mid + 1;

		while (p1 <= mid && p2 <= end) {
			if (tmp[p1] > tmp[p2]) {
				arr[k] = tmp[p2];
				k++;
				p2++;
			} else {
				arr[k] = tmp[p1];
				k++;
				p1++;
			}
		}

		// 한쪽 그룹이 모두 선택된 후 남아있는 값을 정리하기
		// -> 그룹끼리 재정렬 -> while문을 이용해 끝까지 반복
		while (p1 <= mid) {
			arr[k] = tmp[p1];
			k++;
			p1++;
		}
		while (p2 <= end) {
			arr[k] = tmp[p2];
			k++;
			p2++;
		}
	}
}

문제 21. 버블 소트 프로그램2

버블 소트는 서로 인접해 있는 두 수를 바꾸면서 정렬하는 방법이다. 예를 들어 수열이 3, 2, 1 이었다고 가정해 보자. 이때는 인접해 있는 3, 2가 바뀌어야 하므로 2, 3, 1 이 된다. 그다음은 3,1 이 바뀌어야 하므로 2,1,3이 된다. 그다음에는 2,1 이 바뀌어야 하므로 1,2, 3이 된다. 그러면 더 이상 바꿀 수 없으므로 정렬이 완료된다.


N개의 수로 이뤄진 수열 A[1], A[2], …，A[N]이 있다. 이 수열로 버블 소트를 수행할 때 swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

 

입력
1 번째 줄에 N(1 <= N <= 500,000), 2번째 줄에 N개의 정수로 A[1], A[2], …，A[N]이 주어진다. 각각의 A[i]는 0 < =|A[i]| <= 1,000,000,000의 범위에 들어 있다.

 

출력
1 번째 줄에 swap 횟수를 출력한다.

 

예제 입력

8 //수의 개수
3
2
8
1
7
4
5
6

예제 출력

11

1단계. 문제 분석하기

: N의 최대 범위가 1,000,000이므로 O(nlongn)의 시간 복잡도로 정렬 수행

-> 버블 소트를 사용할 경우 제한 시간 초과 -> 병합 정렬 사용 -> 병합 정렬에 버블 정렬의 원리인 swap 연산이 포함

 

-> 버블 정렬을 여러번 사용한 효과를 병합 정렬을 한번만 사용해도 같은 결과

 

2단계. 손으로 풀어보기

: 병합 정렬의 정렬 과정에서 index가 이동한 거리를 result에 저장

-> 즉, raw 배열에서 이동한 거리를 계산해 result에 저장하면 된다.

 

3단계. 슈도코드 작성하기

: 병합 정렬과 동일한데, swap 횟수를 세기 위한 로직만 추가한다.

N(정렬할 수 개수)
A(정렬할 배열 선언하기)
tmp(정렬할 때 잠시 사용할 임시 배열 선언하기)
for(N의 개수만큼)
{
A 배열 선언하기
}
병합 정렬 함수 수행하기
결괏값 출력하기
// 병합 정렬 수행하기
병합 정렬(s, e) {
s(시작점), e(종료점), m(중간점)
// 재귀 함수 형태로 구현하기
병합 정렬(s, m)
병합 정렬(m + 1, e)
for(s ~ e)
{
tmp 배열 저장하기
}
// 두 그룹을 병합하는 로직
index1 — 앞쪽 그룹 시작점
index2 - 뒤쪽 그룹 시작점
while (index1 <= 중간점 && index2 <= 종료점) {
뒤쪽 데이터 값이 더 작아 선택될 때
swap이 일어났다고 가정하고、현재 남아 있는 앞쪽 데이터 개수만큼 결왓값을 더함
}
반복문의 끝난 후 남아 있는 데이터 정리하기
}

 

 

package sorting.ch04;

import java.util.Scanner;

public class sorting_q21 {

	// 매번 파라미터로 보내지않고, static으로 선언
	public static int[] arr, tmp;
	public static long result;

	public static void main(String[] args) {
		sorting_q21 T = new sorting_q21();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		arr = new int[n + 1];
		tmp = new int[n + 1];
		for (int i = 1; i <= n; i++)
			arr[i] = kb.nextInt();

		T.sort(1, n);
		System.out.println(result);

	}

	private void sort(int start, int end) {
		// 최소 길이로 분할 -> 처음부터 중간점까지 집합 1, 중간점+1부터 마지막까지 집합2
		// -> 각각 정렬하는 로직
		if (end - start < 1) return;
		int mid = start + (end - start) / 2;

		sort(start, mid);
		sort(mid + 1, end);

		for (int i = start; i <= end; i++) tmp[i] = arr[i];

		// 두 그룹을 병합하는 로직
		// -> 양쪽 그룹의 index가 가리키는 값을 비교해 더 작은 수를 선택해 배열에 저장하고,
		// 선택된 데이터의 index 값을 오른쪽으로 한 칸 이동하기
		int k = start;
		int p1 = start;
		int p2 = mid + 1;

		while (p1 <= mid && p2 <= end) {
			if (tmp[p1] > tmp[p2]) {
				arr[k] = tmp[p2];
                result = result+p2-k;
				k++;
				p2++;
			} else {
				arr[k] = tmp[p1];
				k++;
				p1++;
			}
		}

		// 한쪽 그룹이 모두 선택된 후 남아있는 값을 정리하기
		// -> 그룹끼리 재정렬 -> while문을 이용해 끝까지 반복
		while (p1 <= mid) {
			arr[k] = tmp[p1];
			k++;
			p1++;
		}
		while (p2 <= end) {
			arr[k] = tmp[p2];
			k++;
			p2++;
		}
	}
}
반응형
저작자표시 비영리

'Java > Java 알고리즘' 카테고리의 다른 글

[알고리즘] 2. 자료구조  (0) 2022.06.28
[알고리즘] 1-6. 기수 정렬 [구간 합 이용] (+ 우선순위 큐 이용)  (0) 2022.06.28
[알고리즘] 1-4. 퀵 정렬 [재귀 함수 이용]  (0) 2022.06.28
[알고리즘] 1-3. 삽입 정렬 #  (0) 2022.06.27
[알고리즘] 1-2. 선택 정렬 #  (0) 2022.06.27

'Java/Java 알고리즘' Related Articles

티스토리툴바