I'm taehee.won.

 합병 정렬 (Merge Sort) 은 데이터 영역을 잘게 쪼개어 정렬을 하는 분할 정복 (Divide and Conquer) 에 기반한 정렬 방법으로, 잘게 쪼갠 데이터들을 하나씩 합병하여 정렬하는 방법이다.(분할 정복과 같은 알고리즘 방법에 대한 이야기는 간단한 알고리즘 정리 이후에 다룰 예정이다.) 구현이 어렵고, 재귀 함수 활용시 추가적인 메모리가 필요하지만, 기초적인 정렬 방법과 비교하여 정렬 속도가 매우 빠르다.

 위의 그림과 같은 단계를 통해서 정렬이 진행된다. 먼저, 전체 데이터 영역을 최소 단위로 쪼갠다. 쪼갠 데이터들을 하나씩 합병할 때에, 정렬을 한다. 이 방식을 반복한다.

 합병 정렬을 다음과 같이 구현하였다.

 데이터 영역의 가운데 위치를 iTemp_CenterPosition 에 저장하고, 이를 기준으로 데이터 영역으로 두개로 나눈다. 두개의 영역을 합병 정렬하도록, 합병 정렬 함수를 재귀적으로 호출한다.(우선적으로 전체 데이터 영역이 최소 단위로 쪼개어진다.) 데이터 영역만큼의 메모리를 추가적으로 할당한뒤, 두개의 영역은 각각 정렬이 되어 있다고 가정하고, 순서대로 값을 비교하여, 합병, 정렬된 데이터 영역을 만든다. 이 방식을 반복한다. 이 정렬 사용하는 예제는 이전 글(링크 : [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선)에서 확인할 수 있다.

 선택 정렬 (Selection Sort) 는 정렬이 되지 않은 데이터 영역에서 최소값을 찾아 데이터 영역의 가장 앞으로 이동하는 방식을 반복하여 전체 데이터 영역을 정렬하는 방법이다. 데이터가 많아질수록 많은 시간이 걸리고, 다른 정렬과 비교하여 장점이 없어, 추천하기 어려운 정렬 방법이다.

 위의 그림과 같은 단계를 통해서 정렬이 진행된다. 정렬이 되지 않은 데이터 영역에서 최소값을 찾아 가장 앞으로 이동한다. 이동한 값을 제외한 정렬이 되지 않은 데이터 영역에서 최소값을 찾아 가장 앞으로 이동한다. 이 방식을 반복한다. 이 방식은 항상 같은 비교 횟수((n-1) + (n-2) +  (n-3) ... + 2 + 1 = n * (n-1)/2 = n(n-1)/2)를 가지게 된다.

 선택 정렬을 다음과 같이 구현하였다.

 정렬이 되지 않은 데이터 영역의 가장 앞 위치를 iTemp_Processing 에 저장하고, iTemp_Compare 가 증가하며 값을 비교하여 가장 작은 값의 위치를 iTemp_MinPosition 저장한다. 마지막으로 iTemp_MinPosition 의 값을 iTemp_Processing 으로 이동한다. 이 방식을 반복한다. 정렬할 때에 사용하는 Swap 함수, 이 정렬 사용하는 예제는 이전 글(링크 : [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선)에서 확인할 수 있다.

 삽입 정렬 (Insert Sort) 는 정렬되어 있는 영역에 새로운 데이터의 정렬 위치를 찾아서 삽입하는 방식을 반복하여 전체 데이터 영역을 정렬하는 방법이다. 데이터가 많아질수록 많은 시간이 걸리지만, 거품 정렬과 비교하여 구현 난이도가 비슷하면서도 성능이 개선된다.

 위의 그림과 같은 단계를 통해서 정렬이 진행된다. 정렬을 하고자하는 데이터 영역에서 1개의 요소는 기본적으로 정렬이 되어 있다고 본다(Step 1). 다음 요소를 이미 정렬되어 있는 데이터 영역에서 위치를 찾아서 삽입한다(Step 2 ~ 5). 이 방식은 기본적으로 거품 정렬과 같은 비교 횟수(1 + 2 + ... + (n-3) + (n-2) + (n-1) = n * (n-1)/2 = n(n-1)/2)를 가지게 된다.

 하지만, 이미 정렬되어 있는 데이터 영역의 가장 큰 요소와 새로 비교하게 되는 요소를 비교하여, 삽입이 필요하지 않을 때에는 1번의 비교만으로 1번의 Step 을 넘어갈 수 있다. 이미 정렬이 되어 있는 경우(최선의 경우), n-1 의 비교 횟수를 가지게 된다. 최선의 경우와 최악의 경우의 비교 횟수 평균은 (n(n-1)/2 + (n-1))/2 = (n^2 + n - 2)/4 가 된다. 최선의 경우와 최악의 경우의 평균만을 확인해보았지만, 이미 정렬된 데이터 영역에서는 새로운 요소를 모두 비교할 필요없이 자신의 위치를 찾을 수 있으므로, 정렬의 효율이 개선된다.

 삽입 정렬을 다음과 같이 구현하였다.

 iTemp_Processing 은 새로 비교하게 되는 요소의 위치를 저장하며, iTemp_Compare 가 이미 정렬되어 있는 데이터 영역에서 증가하며 값을 비교한다. 정렬할 때에 사용하는 Swap 함수, 이 정렬 사용하는 예제는 이전 글(링크 : [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선)에서 확인할 수 있다.

 칵테일 정렬을 한마디로 표현하면, 거품 정렬의 최종 개선판이라고 할 수 있다.

 앞서 개선한 거품 정렬은 한번 비교가 필요없는 데이터 구간이 결정되면 단계마다 그만큼의 연산이 줄어들기 때문에 효율이 좋아지지만, 한번 비교 연산이 줄어들고 나면, 추가적인 효율이 크게 발생하기 어렵다.

 추가적으로 큰 효율 증가를 기대하기 위해서 거품 정렬을 이전에 한 것과 반대 방향으로 이용하는 방식을 번갈아 사용하도록 개선한다.

 위의 그림과 같이 데이터 집합을 한번은 순서대로 거품 정렬하고, 한번은 역순으로 거품 정렬하는 방식으로 정렬을 하며, 앞서 개선한 방법을 이용하여 더 이상 정렬이 필요없는 구간을 다시 비교하지 않도록 한다.

 다음과 같이 구현하였다.

 기존에 For 구문이 한 단계씩 진행되는 것이었다면, While 구문으로 두 단계씩 묶어서 정렬한다. 거품 정렬과 동일한 방식으로 인접한 두 개의 데이터를 비교하는 것을 반복하여 정렬한다. 정렬할 때에 사용하는 Swap 함수, 이 정렬 사용하는 예제는 이전 글(링크 : [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선)에서 확인할 수 있다.

 거품 정렬 (Bubble sort) 은 인접한 두 개의 데이터를 비교하는 것을 반복하여 정렬하는 방법이다. 데이터가 많아질 수록 많은 시간이 걸리지만, 코드가 단순하여 구현하기 쉽다. 거품이라는 이름은 데이터가 거품이 수면으로 올라가듯 정렬되는 모습에서 지어진 이름이다.

 위의 그림과 같은 단계를 통해서 정렬이 진행된다. 처음부터 시작해서 인접한 데이터를 비교해서 큰 값이 뒤에 위치하도록 한다. 데이터 전체를 한번 반복하게 되면, 가장 큰 값이 수의 집합에서 마지막에 위치하게 된다. 그럼 마지막에 위치한 값을 빼고 다시 처음부터 같은 방식으로 정렬한다. 이 방식은 항상 같은 비교 횟수((n-1) + (n-2) + (n-3) ... + 2 + 1 = n * (n-1)/2 = n(n-1)/2)를 가지게 된다.

 거품 정렬을 다음과 같이 구현하였다.

 비교는 항상 다음 위치의 값과 비교되므로, 데이터 집합의 처음부터 마지막에서 한개 전의 데이터까지 반복한다. Temp_Complete 는 Step 에 따라 줄어드는 데이터 집합의 크기를 저장하며, iTemp_Compare 가 증가하며, 값을 비교하며 정렬한다.

 아래의 함수는 비교 이후, 두개의 값이 바뀌어야 할 때에 값을 바꾸어 주는 Swap 함수이다.

 거품 정렬을 사용하는 예제이다.

 앞으로의 정렬 예제에서는 위의 정수형 배열의 값을 출력하는 출력함수를 이용하여, 정상적으로 정렬이 되었는지 확인한다.

 "4, 2, 1, 5, 3, 8, 5, 3, 1, 4" 의 데이터 집합을 만들고, 거품 정렬을 이용하여 정렬한다.

 위와 같이 올바르게 정렬된 것을 확인할 수 있다.

 거품 정렬은 추가적인 메모리 사용이 없는 대신, 효율이 좋지 않다. 이를 개선하였다.

 위의 그림을 보면, Step 1 에서 2 번의 비교 후, 데이터 위치 교체를 하고나면, 더 이상의 교체는 일어나지 않는다. 데이터 위치 교체 이후의 값들은 이미 데이터 집합에서 최대값이 순서대로 정렬되어 있음을 의미한다. 3 번째에서부터 7 번째까지의 비교 연산은 다음 Step 부터는 필요가 없다. 이를 개선했을 경우에는 데이터 집합의 후반부에 정렬되어 있는 값들은 다시 비교하지 않아 효율을 올릴 수가 있다.

 다음과 같이 거품 정렬을 개선하여 구현하였다.

 iTemp_LastSwap 변수를 추가하여, 데이터 교체가 일어났을 때의 위치를 저장하였다가 다음 단계로 넘어갈 때에, 사이즈를 증가시켜서 다시 비교하여 정렬할 필요가 없는 구간을 다시 비교하지 않도록 개선하였다.

 전산학과 수학에서 정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 흔히 유용하게 쓰인다. 이 알고리즘의 결과는 반드시 다음 두 조건을 만족해야 한다.

 1. 출력은 비 내림차순(각각의 원소가 완전 순서에 의해 이전의 원소보다 작지 않은 순서)이다.
 2. 출력은 입력을 재배열하여 만든 순열이다.

 컴퓨터의 초창기에, 정렬 알고리즘은 연구하기에 대단히 매력적인 주제였다. 간단하고 익숙하지만, 그것을 효율적으로 풀어내기는 복잡하기 때문일지도 모른다. 예를 들어, 거품 정렬은 1956년에 분석되었다. 수없이 많은 논의를 거쳐왔지만, 쓸만한 새로운 정렬 알고리즘들은 현재도 계속 발명되고 있다. 정렬 알고리즘은 다양한 핵심 알고리즘 개념 (점근 표기법, 분할 정복 알고리즘, 자료 구조, 최악의 경우, 평균적인 경우, 최선의 경우 등) 을 소개하는 데 적당하기 때문에, 컴퓨터 과학 강의에서 입문 과정으로 유행하고 있다.

(참고 : http://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC)

 위키백과의 설명에도 나와 있듯이 정렬 알고리즘은 핵심 알고리즘 개념을 이해하기 좋다. 이에, 정렬 알고리즘을 하나씩 정리하고, 그 이해를 바탕으로 더욱 복잡하고 효율이 좋은 알고리즘을 만들어나가려 한다. 정렬의 이해와 구현을 넘어서서, 각각의 원리와 그 효율을 비교, 분석하려 한다.

 알고리즘이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다.

 정의 : 입력(외부에서 제공되는 자료가 0개 이상 존재한다.), 출력(적어도 1개 이상의 결과를 내어야 한다.), 명확성(수행 과정은 명확하고 모호하지 않은 명령어로 구성될 수 있다.), 유한성(종결성)(유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.), 효율성(모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다)

 분석 기준 : 정확성, 작업량, 기억 장소 사용량, 최적성, 복잡도

(참고 : http://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

 알고리즘은 문제를 해결하기 위한 방법이라고 볼 수 있다. "매일 아빠와 엄마에게 용돈을 받으면, 하루에 내가 받는 용돈은 얼마인가?" 와 같이 간단한 문제에 대한 해답을 찾는 방법부터 "임의의 수의 집합에 특정 수가 존재하는가?" 와 같은 문제에 대한 해답을 찾는 방법, 모두 알고리즘이라고 할 수 있다. 조금의 자원을 사용하여 정확한 답을 찾는 것이 알고리즘의 목표라고 볼 수 있다. 여기에서는 많이 알려진 알고리즘인 정렬, 탐색에서부터 온라인 저지(Online judge) 사이트들에 있는 문제들을 해결한 방법을 하나씩 정리해보려고 한다.

 알고리즘는 내가 블로그를 열게된 이유와도 같다. 알고리즘은 회사 업무에 염증을 느끼던 나에게 다시 한번 프로그래밍의 재미를 일깨워주고, 기초 부분을 하나하나 다시 보면서 몰랐던 내용을 이해하게 해주었다. 여유시간에 자료구조, 알고리즘 관련 책들을 보면서 for, while 등의 반복문을 한번이라도 덜 수행하게 하는 방법이 없는지 고민하면서, 한가지에 몰두하며 시간을 보낼 수 있었다. 이런 재미를 나만이 아닌 다른 누군가도 느끼길 바랬고, 또 내가 알게된 내용을 정리하고자 블로그를 열게 되었다.