I'm taehee.won.

 C 프로그래밍 언어는 1972년 켄 톰슨과 데니스 리치가 벨 연구소에서 일할 당시 새로 개발된 유닉스 운영 체제에서 사용하기 위해 개발한 프로그래밍 언어이다. 켄 톰슨은 BCPL언어를 필요에 맞추어 개조해서 "B" 언어(언어를 개발한 벨 연구소의 B를 따서)라 명명했고, 데니스 리치가 이것을 개선하여 C언어가 탄생했다. 유닉스 시스템의 바탕 프로그램은 모두 C로 쓰여졌고, 많은 운영 체제의 커널도 또한 C로 만들어졌다. 오늘날 많이 쓰이는 C++는 C에서 객체 지향형 언어로 발전된 것이다. 또 다른 다양한 최신 언어들도 그 뿌리를 C에 두고 있다.

 C는 실질적으로 모든 컴퓨터 시스템에서 사용할 수 있는 프로그래밍 언어이다. 예를 들어 BASIC 등과는 달리 다양한 플랫폼에서 ANSI C의 정의에 따르는 비교적 동일한 구현이 가능하다. 모든 C 시스템에는 정규화된 표준 C 라이브러리가 존재한다. 이런 이유와 생성된 프로그램의 높은 성능이 아직까지도 C언어가 사랑받는 이유 중 하나이다.

 그러나 C 언어가 기술적으로 보아 현재 기술 수준에 부합하지 않는다는 의견이 있으며, C를 "이식가능한 고급 어셈블리어" 정도로 낮추어 부르기도 한다. 이는 반면 오늘날의 널리 쓰이는 거의 모든 운영 체제 커널이 C를 이용해 구현된 이유이기도 하다. C는 시스템 프로그램 개발에 매우 적합하나, 응용 프로그램 개발에도 많이 쓰인다.
(참고 : http://ko.wikipedia.org/wiki/C%EC%96%B8%EC%96%B4)

 프로그래밍에 대해서 조금이라도 이야기를 들은 적이 있는 사람이라면 C 언어에 대해서 안 들어본 사람은 없을 것이다. 그 만큼 프로그래밍의 기본이 되는 언어로 시초라고 볼 수 있다. 현재, 많이 사용되고 있는 C++ / C# / JAVA 등의 언어들은 그 기반을 C 에 두고 있다. 이 말은, C 언어에서 사용되고 있는 모든 개념이 다른 모든 언어에서 사용되며, 다른 언어들은 C 언어에서 확장된 개념들을 "더" 가지고 있을 뿐이라는 이야기가 된다.

 나는 프로그래밍을 배우는 이들에게 C 언어로 시작하기를 권한다. 이는 사람이 "걷는 법" 을 배우고, "뛰는 법" 을 배웠다고, 뛰기만 하지는 않는다는 것이 적절한 예가 될지 모르겠다. 처음부터 "뛰는 법" 을 배운다고, "걷는 법" 을 모르는 것은 아니지만, 그만큼 기본이 중요하다. C 언어를 익힌다는 것은 그 기본을 배운다는 것이고, "1" 이라는 것을 "일" 이라고 표현하느냐, "하나" 라고 표현하느냐의 차이는 차후 다른 언어들을 익혀나가면 될 것이다.

 프로그래밍은 단순히 언어를 잘 익히고, 구현을 잘 하는 것이 아니다. 시스템을 이해하고, 구현을 어떻게 할지에 대한 설계를 잘 하는 것이 중요하다. 프로그래밍 언어는 그것을 실현시켜줄 도구에 불과하다는 사실을 잊어서는 안된다.

 합병 정렬 (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) 정의 / 코드 / 개선)에서 확인할 수 있다.

 지금까지 만든 스택 연결 리스트가 올바르게 동작하는지 확인하기 위한 출력 함수를 구현하였다.

스택 연결 리스트의 데이터의 입력, 출력이 일어날 Top 의 위치, 데이터를 출력한다.

 스택 연결 리스트의 선언부 이다.(Stack.h)

 스택 연결 리스트의 생성과 관련된 함수(ifCreateStackLinkedList), 소멸과 관련된 함수(ifDestroyStackLinkedList), 기본 기능과 관련된 함수(vfPushStackLinkedList, unfPopStackLinkedList, unfTopStackLinkedList, ifEmptyStackLinkedList) 로 이루어져 있다. 필요에 따라 함수를 수정, 추가, 구현하거나, 저장되는 자료형을 추가한 후, 생성함수를 수정하여 사용할 수 있다.

 스택 연결 리스트의 구현부 이다.(Stack.c)

 마지막으로 스택 연결 리스트를 사용하는 예제이다.

 vfPrintStackLinkedList 함수가 호출되는 시점을 기준으로 다음과 같이 3 단계로 나눌 수 있다.

1 단계 : 스택을 생성한 후, "1, 2, 3, 4, 5" 를 스택에 Push(데이터 저장)

2 단계 : 스택에서 2 번 Pop(데이터 제거)

3 단계 : 스택의 가장 마지막 데이터 출력

 연결 리스트 (Linked List) 로 스택을 구현하려 한다. 연결 리스트로 스택을 구현하면, 배열 스택의 단점인 고정된 데이터 저장 공간이라는 점을 극복할 수 있다. 아래의 그림과 같이 스택을 연결 리스트로 구현할 것이다. 단순 연결 리스트 (Single Linked List) 로 구현하되, 마지막 노드를 가리키는 포인터 변수를 저장하여 Push 와 Pop 연산시, 마지막 노드를 탐색하는 시간을 줄이도록 한다.

  다음은 스택 연결 리스트 구조체의 선언이다.

 데이터가 저장되는 리스트의 첫번째 노드, 마지막 노드를 가리키는 포인터 변수를 저장한다.

 다음은 스택 연결 리스트의 생성 함수, 스택 연결 리스트의 사용이 끝났을 때, 해당 메모리를 반환하는 함수이다.

 다음은 스택의 기능인 Push(데이터 저장), Pop(데이터 제거), Top, Empty 함수이다.

 가장 위의 그림에서 보여준 것과 같이 기능을 구현하였다. 단순 연결 리스트는 이전에 구현하였으므로, 구현해놓은 헤더파일(SingleLinkedList.h) 을 포함시켜서 이용하였다. Push(데이터 저장), Pop(데이터 제거) 함수는 기능상 동일하나, 단순 연결 리스트이므로, Pop 시에 이전 노드를 가리키기 위한 연산이 추가되었다. 이 연산을 더 효율적으로 하기 위해서는 이중 연결 리스트 (Double Linked List) 로 구현하면 된다.

 연결 리스트 스택은 배열 스택과 달리 스택이 Full 인지를 확인할 필요가 없다. 메모리를 데이터에 맞게 할당받아 저장하기 때문에 필요에 따라 계속해서 데이터를 저장할 수 있다.

 지금까지 만든 스택 배열이 올바르게 동작하는지 확인하기 위한 출력 함수를 구현하였다.

 스택 배열의 크기, 데이터의 입력, 출력이 일어날 Top 의 위치, 데이터를 출력한다.

 스택 배열의 선언부 이다.(Stack.h)

 스택 배열의 생성과 관련된 함수(ifCreateStackArray), 소멸과 관련된 함수(ifDestroyStackArray), 기본 기능과 관련된 함수(ifPushStackArray, unfPopStackArray, unfTopStackArray, ifEmptyFullStackArray) 로 이루어져 있다. 필요에 따라 함수를 수정, 추가, 구현하거나, 저장되는 자료형을 추가한 후, 생성함수를 수정하여 사용할 수 있다.

 스택 배열의 구현부 이다.(Stack.c)

 마지막으로 그 동안 구현한 스택 배열을 사용하는 예제이다.

 vfPrintStackArray 함수가 호출되는 시점을 기준으로 다음과 같이 3 단계로 나눌 수 있다.

1 단계 : 배열의 크기를 10 으로 스택을 생성한 후, "1, 2, 3, 4, 5" 를 스택에 Push(데이터 저장)

2 단계 : 스택에서 2 번 Pop(데이터 제거)

3 단계 : 스택의 가장 마지막 데이터 출력

 이해하기 쉬운 배열로 스택을 구현하려 한다. 배열로 스택을 구현하면, 데이터에 접근하기가 쉽고, 구현이 간단하다는 장점이 있다. 하지만, 메모리를 고정하여 사용하기 때문에, 처음에 구성된 스택의 크기를 벗어나는 데이터를 저장할 수 없다는 단점이 있다. 아래의 그림과 같이 스택을 배열로 구현할 것이다. 고정된 크기의 배열을 생성하고, Top 위치를 저장하고 있다가 Push, Pop 등의 연산을 통해 데이터를 저장하고, 제거할 것이다.

 다음은 스택 배열 구조체의 선언이다.

 스택 배열의 크기, 그리고 데이터의 입력, 출력이 일어날 Top 의 위치, 데이터 메모리 주소를 저장한다.

 다음은 스택 배열의 생성 함수, 스택 배열의 사용이 끝났을 때, 해당 메모리를 반환하는 함수이다.

 처음에 요청된 스택 배열의 크기만큼의 데이터 공간을 가지고 있게 된다.

 다음은 스택의 기능인 Push(데이터 저장), Pop(데이터 제거), Top, Empty 함수이다.

 가장 위의 그림에서 보여준 것과 같이 기능을 구현하였다. Push(데이터 저장) 함수는 스택의 데이터 공간의 가장 위에 데이터를 저장하고, 가장 위를 저장하는 변수를 증가시킨다. 반대로 Pop(데이터 제거) 함수는 스택의 데이터 공간의 가장 위의 데이터를 반환하고, 가장 위를 저장하는 변수를 감소시킨다.

 일반적으로 사용되는 함수와 다르게 구현한 부분은 Empty 함수이다. 일반적으로 Empty 인지를 반환하는 함수인데, 여기서는 Empty 와 Full 여부를 반환하도록 구현하였다. 이를 통하여, Push 전에 Full 인지를 확인하여, 스택의 데이터 공간이 모두 사용 중이면, Push 를 하지 않거나, Pop 전에 Empty 인지를 확인하여, 스택의 데이터 공간이 하나도 사용하지 않고 있다면, Pop 을 하지 않는 용도로 사용할 수 있다.

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

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

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

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

 다음과 같이 구현하였다.

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