I'm taehee.won.

 삽입 정렬 (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 인지를 확인할 필요가 없다. 메모리를 데이터에 맞게 할당받아 저장하기 때문에 필요에 따라 계속해서 데이터를 저장할 수 있다.