[cs50] 합병정렬(Merge Sort)과 이진탐색
합병정렬은 이전까지의 방법과는 달리 많은 양의 데이터가 한 개가 될 때까지 반으로 계속 분해한다. 그리고 다시 그 데이터를 합치는 것을 합병정렬이라 한다. 이 정렬방식의 효율성에 대해 알아보자.
1. 합병 정렬
전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있는 방법인 합병 정렬(병합 정렬)이 있습니다. 합병 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다. 그리고 이 과정은 재귀적으로 구현되기 때문에 나중에 재귀를 학습하면 더 이해하기 쉽습니다.
-> half씩 처리하며 자기 스스로 계속 불러내는 재귀의 형식을 띈다. 아무래도 메모리를 많이 차지한다는 단점이 있지만, 요즘 하드웨어가 상대적으로 저렴한 편이니 합병정렬이 알맞은 상황에 맞게 쓰면 되겠다.
실행
합병 정렬의 시간복잡도
분할 정복은 모든 데이터를 다 보는 것이 아니라 절반을 그리고 그 절반을 보는 방식으로 진행되어 탐색 시간이 굉장히 짧았던 것을 기억하시나요? 합병 정렬 역시 반을 나눈다는 개념이 사용되기 때문에 시간이 적게 들 것이라고 유추할 수 있습니다.
만약 8개의 원소가 있다면 3번 나누어질 것입니다. 따라서 n개의 원소가 있을 때 완전히 다 나누어지기까지 호출되는 함수의 개수는 log n개라는 것을 알 수 있습니다. 그리고 합병 정렬은 병합하는 알고리즘을 포함합니다. 합쳐지는 과정에서 각 원소들의 크기를 비교하기 때문에 n번의 비교 과정이 있습니다. 즉 한번 나누어질 때마다 n번의 비교 횟수가 추가되는 것입니다. 따라서 합병 정렬의 시간 복잡도는 Ο(n log n)입니다.
-> 퀵소트와 비교하면, 중간에 공간(메모리)를 더 차지한다는 점이므로 여유공간이 없을 때는 퀵 소트를 사용하면 된다.
2. 이진 탐색
주어진 배열을 탐색하는데 사용할 수 있는 다양한 알고리즘이 있습니다. 그중 하나는 선형 탐색이라는 것인데 이것은 시간이 다소 오래 걸릴 수 있습니다. 만약 여러분이 찾고자 하는 원소가 배열의 끝에 있다고 가정해봅시다. 선형 알고리즘을 사용하면 찾고자 하는 원소를 찾기 위해 배열 전체를 탐색해야 합니다. 선형 탐색보다 더 빠른 알고리즘으로 이진 탐색이 있습니다. 이진 탐색은 자료를 절반으로 나눈 후 찾는 값이 어느 쪽에 있는지 파악해 탐색의 범위를 반으로 줄여나가는 탐색 알고리즘입니다.
효율성과 비효율성
배열을 정렬하는 데는 버블 정렬, 삽입 정렬, 선택 정렬 등 다양한 방법이 있습니다. 이 정렬 방법은 사실 이진 탐색을 구현하는 데 유용합니다. 이진 탐색의 기본은 정렬된 배열을 만들 수 있다는데 가정을 두고 있습니다. 이진 탐색 의사 코드인 <코드 1>을 참고하여 배열에서 50을 찾아봅시다.
이진 탐색 vs 선형 탐색
우리가 어떤 부분을 좋게 만들면 반드시 다른 부분에서 비용이 발생한다는 것은 컴퓨터 과학에서는 일반적인 사실입니다. 이진 탐색은 일반적으로 선형탐색보다 탐색 속도가 짧지만, 배열을 정리하는 시간이 추가됩니다. 그렇기 때문에 선형적으로 배열을 탐색하는 것이 배열을 정렬한 후 이진 탐색을 사용하는 것보다 빠르게 보이기도 하고, 사실 어떤 상황에서는 이것이 사실이기도 합니다.
하지만 배열을 여러 번 탐색할 계획하고 있다면 이진 탐색이 유용하게 사용됩니다. 찾고자 하는 값이 배열에 없는 경우 선형 탐색은 배열의 길이가 얼마든 상관없이 배열 전체를 훑어보아야 배열 안에 찾고자 하는 값이 없다는 것을 알 수 있습니다. 이에 반해 이진 탐색에서는 더 효율적으로 사용할 수 있습니다. 의사 코드를 수행해보면, 찾고자 하는 값이 최소값보다 작거나 최대값보다 크다면 해당 원소가 배열 안에 없다는 것을 알 수 있습니다.