Intro
개발자가 되기 위해 노력하는 동생이 있다.
이 동생은 서울42를 수강한 경험이 있고, 해당 학습 과정에서 라이브러리 사용을 제한 당한다.
이 동생은 이러한 상황에서도 코딩을 해야한다. 정확히는 서울42 모두가 그렇다.
그렇기 때문에 라이브러리를 직접 구현하는 방식으로 코딩을 구현하게 되며 정렬에 관해서는 모든 것을 구현해 봤으며 이에 대한 이해도가 높아졌다고 이야기 해주었다.
부러웠다. 그리고 멋있었다. 라이브러리라는 똑똑한 사람들이 만들어둔 걸 단순히 사용하는 게 아니라, 만약 문제가 있다면 언제든지 뜯어서 고칠 수 있고, 동작 과정이 단순하게 개념이나 영상 같은 것으로 이해하고 있는게 아니라 코드로 직접 구현할 수 있다는 것이 상당히 매력적이라고 생각했다. 삽입정렬, 버블정렬, 선택정렬의 경우 마지막에 총정리 때 가볍게 다루고자 한다.
그렇다면 왜 병합 정렬을 먼저 다루었을까?
그 이유는 다음에 정리하고자 하는 정렬 방식의 소개 때문이다.
TIMSort
나는 현재, 개발자로 취업을 위해 기본 개념의 학습을 마치고 회사에 어플라이를 하고 있다. 이 과정 속에서 계속 성장하고 더 깊이있게 코드를 알아가기 위해 기술에 관련한 스터디도 진행하고 있으며 팀원들 덕분에 많은 것을 배우며 성장하고 있다.
한 팀원이 현재 라이브러리에서 사용되고 있는 정렬의 경우 TIMSort가 라이브러리로 사용되고 있다는 것을 알려주었고 이는 병합정렬과 삽입정렬을 섞은 하이브리드 정렬이라는 것을 알려주었다. 정확히는 그렇게 사용하고 있다고 알고 있는데,
이번 정렬 주제를 준비하셨는데 이 주제에 대해서 알고 있느냐? 라는 질문을 받았을 때
전혀 몰랐다. 그랬기에 학습하고 싶었고, 이를 학습하기 이전에 더 깊이 있게 정렬에 대해서 전체적인 이해도와 학습과정을 정리하면 좋겠다는 생각에서 해당 블로그 내용을 기획하게 되었다.
다음 편에서 다루겠지만 TIMSort는 아래와 같은 특징이 있다.
| 분류 | 정렬알고리즘 |
|---|---|
| 자료구조 | 배열 |
| 최악 시간복잡도 | O(nlogn) |
| 최선 시간복잡도 | O(n) |
| 평균 시간복잡도 | O(nlogn) |
| 공간복잡도 | O(n) |
(출처 : 위키피디아)
다음 편을 통해 더 자세히 알아 보도록 하고,
현재의 병합정렬에 대해서 알아보자 :)
병합정렬(MergeSort)
| 분류 | 정렬알고리즘 |
|---|---|
| 자료구조 | 배열 |
| 최악 시간복잡도 | O(nlogn) |
| 최선 시간복잡도 | O(nlogn) |
| 평균 시간복잡도 | 일반적으로, O(nlogn) |
| 공간복잡도 | O(n) |
(출처 : 위키피디아)
어떠한 경우에도 nlogn이 보장되는 특징을 알 수 있다.
이는 Quicksort의 경우 최악의 경우 N2인 경우 보다 이점이 있다.
이 주제를 가지고 온 이유는 백준 알고리즘 문제를 매일 풀고 있는데, 해당 과정 중 재귀함수를 풀면서 이 문제를 만났다. 처음에는 의사코드를 보는 것만 해도 너무 머리가 아팠는데 지금은 그냥 눈을 감고도 짤 수 있을 정도로 깊이 있게 이해하게 되었으며, 대체로 재귀를 이용해서 Top-down방식으로 구현하는 강의 및 글이 많은데
Bottom-up 방식으로도 코드를 구현한 코드를 함께 첨부한다.
이러한 Bottom-up 방식은 재귀함수를 사용하며 스택이 사용되는 불필요한 메모리 사용이 발생하지 않기 때문에 분명 이점이 있다.
다만, 재귀의 학습을 통해 재귀함수의 이해와 이를 통한 코드 구현력을 높이는 것도 중요하다고 생각하기 때문에 이를 같이 첨부한다.
글의 순서는 다음과 같다.
1. Top-down 방식의 병합 정렬의 구현.
2. Bottom-up 방식의 병합 정렬의 구현.
3. 이를 적용해 볼 수 있는 백준 문제 첨부.(feat.Tip)
4. 참고 링크들.
우선 top-down 방식의 경우를 보자. 이렇게 하면 병합정렬의 근본적인 순서와 방식에 의거한 형태의 구현이 이루어진다.
top-down 방식은 이렇다.
1. Top-down 방식의 병합 정렬의 구현.
import java.util.Arrays;
public class 병합정렬Top_Down {
// 정렬된 부분 배열을 임시로 저장하는 배열
static int[] temp;
// 재귀 함수로써 배열을 두 부분으로 나누고 병합합니다.
private static void merge(int[] result, int before, int after){
if(before < after){
// 중간 인덱스를 계산합니다.
int mid = before + (after-before)/2;
// 배열의 앞부분을 재귀적으로 병합 정렬합니다.
merge(result, before, mid);
// 배열의 뒷부분을 재귀적으로 병합 정렬합니다.
merge(result, mid + 1, after);
// 두 부분을 병합합니다.
mergesort(result, before, mid, after);
}
}
// 두 부분 배열을 병합하는 함수입니다.
private static void mergesort(int[] result, int before, int mid, int after){
int i = before;
int j = mid + 1;
int k = before;
// 두 부분 배열을 비교하여 작은 값을 temp에 저장합니다.
while(i <= mid && j <= after){
if(result[i] <= result[j]){
temp[k] = result[i++];
}
else{
temp[k] = result[j++];
}
k++;
}
// 왼쪽 부분 배열에 남아 있는 요소를 복사합니다.
while(i <= mid){
temp[k++] = result[i++];
}
// 오른쪽 부분 배열에 남아 있는 요소를 복사합니다.
while(j <= after){
temp[k++] = result[j++];
}
// 임시 배열에서 원래 배열로 병합된 결과를 복사합니다.
for(int t = before; t <= after; t++){
result[t] = temp[t];
}
}
public static void main(String[] args) {
// 정렬하고자 하는 배열입니다.
int[] arr = {2,3,1,5};
// 임시 배열을 생성합니다. 이 배열은 원래 배열과 같은 크기여야 합니다.
temp = new int[arr.length];
// 병합 정렬을 호출합니다.
merge(arr, 0, arr.length-1);
// 정렬된 결과를 출력합니다.
System.out.println(Arrays.toString(arr));
}
}
이와 같은 방식은 분할 정복의 형태로, 하나부터 해서 전체가 되는 형태로 구현이 가능하다.
해당 방식이 추후에 문제를 풀며 추적을 하기가 좋은 형태이다.
반면 bottom-up 방식은 결과적으로 정렬이 되고 공간 복잡도가 스택을 사용하지 않아 장점이 있지만 전체적인 과정을 추적하기에는 어렵다는 단점을 가지고 있다.
이점을 꼭 유의하도록 하자.
2. Bottom-up 방식의 병합 정렬의 구현.
import java.util.Arrays;
public class 병합정렬Bottom_Up {
static int[] temp;
// Bottom-up 방식의 병합정렬을 진행합니다.
private static void merge(int[] arr){
int n = arr.length;
for(int size=1; size<n; size *= 2){
for(int i=0; i<n; i += 2*size){
mergesort(arr, i, Math.min(i+size-1, n-1), Math.min(i+2*size-1, n-1));
}
}
}
// 두 부분 배열을 병합하는 함수입니다.
private static void mergesort(int[] result, int before, int mid, int after){
int i = before;
int j = mid + 1;
int k = before;
// 두 부분 배열을 비교하여 작은 값을 temp에 저장합니다.
while(i <= mid && j <= after){
if(result[i] <= result[j]){
temp[k++] = result[i++];
}
else{
temp[k++] = result[j++];
}
}
// 왼쪽 부분 배열에 남아 있는 요소를 복사합니다.
while(i <= mid){
temp[k++] = result[i++];
}
// 오른쪽 부분 배열에 남아 있는 요소를 복사합니다.
while(j <= after){
temp[k++] = result[j++];
}
// 임시 배열에서 원래 배열로 병합된 결과를 복사합니다.
for(int t = before; t <= after; t++){
result[t] = temp[t];
}
}
public static void main(String[] args) {
// 정렬하고자 하는 배열입니다.
int[] arr = {2,3,1,5};
// 임시 배열을 생성합니다. 이 배열은 원래 배열과 같은 크기여야 합니다.
temp = new int[arr.length];
// 병합 정렬을 호출합니s다.
merge(arr);
// 정렬된 결과를 출력합니다.
System.out.println(Arrays.toString(arr));
}
}
코드가 조금 더 이중for문을 사용한다는 특징이 있다. 해당 코드의 경우 정합하게 내용을 추적할 수 있지 않기 때문에, 이에 관해서는 팁으로 이해하는 게 좋다.
3. 이를 적용해 볼 수 있는 백준 문제 첨부.(feat.Tip)
문제 링크
병합정렬1
Tip 해당 문제의 경우 Bottom-up 방식으로 풀기는 어렵다.
이렇게 되는 이유에 대해서 고민해 보면 좋을 것 같다.
-> 고것이 싫다면, 이 경우는 list를 나누고 합치는 경우이기 때문에 전체 숫자를 계속해서 변경하며 변경되었다는 것을 추적하기가 어렵기 때문이다.
4. 참고 링크들.
- 영상 강의
- 여러 강의를 봤지만(https://youtu.be/ctkuGoJPmAE)
동빈나 유튜브 채널만큼 잘 설명되어 있는 경우가 없는 것 같다.- C++이라서 어렵다면 Java -> (https://youtu.be/QAyl79dCO_k)
- Python이 궁금하다면? ->(https://youtu.be/1qraXP11rSU)
- 여러 강의를 봤지만(https://youtu.be/ctkuGoJPmAE)
사실, 이러한 영상 강의는 자신의 언어가 아니더라도, 개념을 익히고, 자신의 코드로 직접 자신이 구조를 생각해 보며 직접 짜는 게 좋다.
:P