1. 병합 정렬
: 분할 정복 [divide and conquer] 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하면서 합치는 알고리즘
-> 시간 복잡도의 평균값은 O(nlogn)으로 준수한 편이다.
(1) 구현 과정
-> 가장 작은 데이터 집합으로 분할 후, [divide]
-> 병합해 가면서 정렬 [conquer]
-> 각각의 집합을 정렬 후 -> 병합 -> 정렬 후 -> 병합 과정을 반복해 전체를 오름차순으로 정렬
: 2개의 그룹을 병합하는 원리를 이용
# 2개의 그룹을 병합하는 과정 [투 포인터 개념 이용]
- 왼쪽 포인터와 오른쪽 포인터의 값을 비교
- 두 포인터가 가리키는 값 중 작은 값을 결과 배열에 추가하고, 해당 포인터를 오른쪽으로 1칸 이동 [우측 시프트 연산]
- 두 포인터 모두 마지막 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
51단계. 문제 분석하기
-> N의 범위를 보고, O(nlogn)의 시간 복잡도를 이용해 정렬 수행
2단계. 손으로 풀어 보기
- 정렬할 그룹을 최소 길이로 분리한다.
- 배열의 길이가 5이므로 2, 2, 1로 나눈다.
- 나눈 그룹별로 병합 정렬을 수행한다.
- 그룹별 index1, index2를 지정해 비교하면서 결과배열에 추가한다.
- 그룹이 3개이므로, 2번째, 3번째 그룹을 병합
- 이어서 병합된 그룹을 대상으로 재정렬한다.
- 병합한 그룹끼리, 정렬을 수행
- 그룹별 index를 비교해 정렬
- 다시 병합 후 정렬
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예제 출력
111단계. 문제 분석하기
: 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 |