[ 정렬들(Selection, Insertion, Bubble, Quick, Merge, Heap, Radix)에 대하여

수행시간, 비교 횟수, Swap횟수를 통한 비교 ]

1) Selection Sort :

분석 : 데이터의 개수가 n개 일 때, 최소값을 선택하는 데 걸리는 시간 = O( n )

-> 최솟값을 선택하여 리스트의 첫 번째 요소와 자리를 바꾼다.

안정성을 만족하지 않고, 전체 시간복잡도는 O( n^2 )을 따른다.

데이터를 0부터 n까지 매번 비교해야 하므로, n(n-1)/2 번 비교하게 되며 O( n^2 ) 이 되고,

Swap횟수는 찾은 최소값과 리스트의 첫 번째 요소와 바꿔주면 되므로, n-1번 수행되어 O( n ) 이 된다.

2) Insertion Sort :

분석 : 리스트의 값들을 순회하며 리스트에서 정렬이 필요한 데이터는 적당한 곳에 삽입해나간다.

정렬되어 있는 부분에 새로운 레코드를 적절한 위치에 삽입해야하는 과정을 반복해야 한다.

안정성이 보장되고 이미 정렬되어있으면 O(n)이 되어 효율적이지만, 삽입하는 과정이 있으므로 데이터가 많고 정렬이 되어있지 않다면 비효율적이다.

Worst Case는 데이터가 역순으로 정렬되어 있는 경우이며, 비교 횟수는 매번 데이터들의 값을 비교하여 위치를 옮겨주는 과정을 수행해야 하므로, n(n-1)/2 번 비교하며,

Swap은 데이터를 매번 비교하여 이동하는 횟수( n(n-1)/2 ) 에, 데이터가 n개일 때, 처음 인덱스에 대하여 n-1번 만큼 수행해야 하므로 n(n-1)/2 +(n-1) = O( n^2 ) 이 되고, 결과적으로 비교 횟수와 Swap횟수 둘 다 O( n^2 )이 된다.

3) Bubble Sort :

분석 : 인접한 리스트의 요소를 매번 비교해야 하고, 비교 시마다 인접한 요소가 정렬이 되어 있지 않다면 Swap을 해야하므로, 비교 횟수의 경우에는 항상 n(n-1)/2 번 비교하게 되며,

Swap의 경우에는 Best Case의 경우에는 이미 정렬되어 Swap하지 않아도 되는 경우이므로 0이지만, Worst Case의 경우일 때에는 비교와 같이 n(n-1)/2 번 수행해야 하므로, 비교 횟수와 Swap횟수 둘 다 O( n^2 ) 이 된다.

4) Quick Sort :

분석 : 평균적으로 가장 빠르다고 알려져 있는 정렬방법이다. 리스트를 O( n )만큼 추가적으로 할당하여 정렬하는 방법이 있긴 하지만 Stable하고 In-place하지 않으므로 보통은 추가적인 메모리를 더 필요로 하지 않는 방법을 사용한다.

pivot값을 세우고, 이 pivot값을 기준으로 왼쪽과 오른쪽을 분할하여 각각의 부분을 다시 재귀적으로 정렬하는 방법이다.

(pivot 값을 median, 즉 리스트의 중간 값으로 설정하게 되면 Worst case를 피할 수 있는 확률이 더 높아지기 때문에 효율이 높아지게 된다.)

Best Case는 왼쪽과 오른쪽 분할된 부분의 크기가 거의 균등하게 분할되는 경우이며, 분할된 Level의 크기는 logn 이며, 각 분할된 부분에 대하여 비교를 수행하는 횟수는 n 이므로, 비교 횟수는 O(logn) 이 된다.

그러나 Worst Case의 경우에는 왼쪽과 오른쪽이 불균등하게(한쪽은 1개, 한쪽은 n-1개) 분할되는 경우이며,

분할된 Level의 크기가 n 이 되고, 분할된 부분에 대하여 비교를 수행하는 횟수는 n 이므로 총 비교 횟수는 O( n^2 ) 이 되고, Swap횟수는 분할된 부분에 대하여만 Swap을 수행하면 되므로 비교 횟수보다 항상 적다.

5) Merge Sort :

분석 : 리스트를 두 개로 분할하는 과정을 재귀적으로 수행한 후, 다시 올라오며 각각을 정렬하며 합쳐지는 과정을 수행한다. 분할할 때에는 정렬을 하지 않으며, 전부 분할 한 후에 다시 분할된 부분을 합치며 정렬을 수행하는 방식이다.

Best Case, Worst Case에 관계없이 퀵 정렬의 이상적인 분배를 위하여 항상 균등 분할을 하게 되며, 분할된 Level의 크기는 logn 이 되며, 각 분할된 부분에서 n 번의 비교가 수행된다. 따라서 비교 횟수는 O(nlogn) 이 된다.

Swap의 경우 각 분할된 부분에서 ( n *2)번의 Swap이 수행되므로 비교 횟수는 O(nlogn) 이 된다.

6) Heap Sort:

분석 : Heap에서는 각 노드는 자식 노드의 값보다 작으면 안 된다는 성질을 가지고 있다.

n개의 노드에 대하여 완전이진트리는 log(n+1) 의 Level을 가지므로 평균 시간복잡도는 O( nlogn )이 되며,

최악의 경우에 비교는 매번 Heapify를 통해 힙을 재구성 하는 부분에서 Level의 크기( logn )에 대하여 n번 비교를 하게 되므로, O( nlogn )이 되고, Swap횟수는 heapify에서 매번 Swap이 일어나는 경우에, 루트노드와 마지막 노드를 바꿔주는 수행 횟수도 더해주어야 하므로, O( nlogn ) + O(n) = O( nlogn ) 이 된다.

7) Radix Sort:

분석 : 리스트의 전체를 비교하는 것이 아니라, 자리 수를 이용하여 정렬하는 방법이다.

현재 일반적인 정렬 방법의 가장 효율적인 시간복잡도는 O( nlogn )이지만, 이것보다 더 좋은 효율을 낼 수 있는 방법이기도 하지만, 정렬할 수 있는 타입이 숫자와 같이 제한적이라는 단점이 있고, 큐 방식을 이용하여 자릿수에 따라 분할하기 때문에 비교나 Swap횟수는 따로 수행하지 않아 0이 된다.

아래의 그림은 테스트 데이터(정수)의 갯수 n을 각각 100개, 1000개, 10000개, 50000개로 했을 때의 Swap횟수와 비교횟수, 수행시간의 데이터이다.

C Shell Sort로 오름차순 정렬하는 방식입니다.

시간복잡도 : O(n^2) - Worst case

Best case : O(n), Average Case : O(n^1.25)

#include <stdio.h>

void printArray(int value[], int count) {

int i = 0;

for (i = 0; i < count; i++)

printf("%d ", value[i]);

printf("\n");

}

void shellInsertionSort(int value[], int start, int end, int interval) {

int i = 0, item = 0, index = 0;

for (i = start + interval; i <= end; i = i + interval) {

item = value[i];

index = i - interval;

while ((index >= start) && item < value[index]) {

value[index + interval] = value[index];

index = index - interval;

}

value[index + interval] = item;

}

}

void shellSort(int value[], int count) {

int i = 0, interval = 0;

interval = count / 2;

while (interval >= 1) {

for (i = 0; i < interval; i++)

shellInsertionSort(value, i, count - 1, interval);

printf("Interval-%d, ", interval);

printArray(value, count);

interval = interval / 2;

}

}

int main(int argc, char *argv[]) {

int values[] = { 80, 50, 70, 10, 60, 20, 40, 30 };

printf("Before shellSort\n");

printArray(values, 8);

shellSort(values, 8);

printf("\nAfter Sort\n");

printArray(values, 8);

return 0;

}

C Merge Sort로 오름차순 정렬하는 방식입니다.

시간복잡도 : O(nlogn)

#include <stdio.h>

#include <stdlib.h>

void printArray(int value[], int count) {

int i = 0;

for (i = 0; i < count; i++)

printf("%d ", value[i]);

printf("\n");

}

void mergeSortInternal(int value[], int buffer[], int start, int middle, int end) {

int i, j, k, t;

i = start;

j = middle + 1;

k = start;

while (i <= middle && j <= end) {

if (value[i] <= value[j]) {

buffer[k] = value[i];

i++;

}

else {

buffer[k] = value[j];

j++;

}

k++;

}

if (i > middle) {

for (t = j; t <= end; t++, k++)

buffer[k] = value[t];

}

else {

for (t = i; t <= middle; t++, k++)

buffer[k] = value[t];

}

for (t = start; t <= end; t++)

value[t] = buffer[t];

printf("start-%d, middle-%d, end-%d, ", start, middle, end);

for (t = start; t <= end; t++)

printf("%d ", value[t]);

printf("\n");

}

void mergeSort(int value[], int buffer[], int start, int end) {

int middle = 0;

if (start < end) {

middle = (start + end) / 2;

mergeSort(value, buffer, start, middle);

mergeSort(value, buffer, middle + 1, end);

mergeSortInternal(value, buffer, start, middle, end);

}

}

int main(int argc, char *argv[]) {

int values[] = { 80, 50, 70, 10, 60, 20, 40, 30 };

int *pBuffer = NULL;

pBuffer = (int *)malloc(sizeof(values));

printf("Before mergeSort\n");

printArray(values, 8);

if (pBuffer != NULL) {

mergeSort(values, pBuffer, 0, 7);

free(pBuffer);

}

printf("\nAfter Sort\n");

printArray(values, 8);

return 0;

}

C Quick Sort로 오름차순 정렬하는 방식입니다.

시간복잡도 : O(n^2) - Worst Case 일 때 이지만,

일반적으로는 가장 빠른 정렬으로 시간복잡도를 O(nlogn) 으로 봅니다.

#include <stdio.h>

void printArray(int value[], int count) {

int i = 0;

for (i = 0; i < count; i++)

printf("%d ", value[i]);

printf("\n");

}

void quickSort(int value[], int start, int end) {

int pivot = 0;

if (start < end) {

pivot = partitionQuickSort(value, start, end);

quickSort(value, start, pivot - 1);

quickSort(value, pivot + 1, end);

}

}

int partitionQuickSort(int value[], int start, int end) {

int pivot = 0, temp = 0, left = 0, right = 0;

left = start;

right = end;

pivot = end;

while (left < right) {

while ((value[left] < value[pivot]) && (left < right))

left++;

while ((value[right] >= value[pivot]) && (left < right))

right--;

if (left < right) {

temp = value[left];

value[left] = value[right];

value[right] = temp;

printf("start-[%d], end-[%d], pivot-[%d], in-loop, ", start, end, value[pivot]);

printArray(value, end - start + 1);

}

}

temp = value[pivot];

value[pivot] = value[right];

value[right] = temp;

printf("start-[%d], end-[%d], pivot-[%d], out-loop, ", start, end, value[right]);

printArray(value, end - start + 1);

return right;

}

int main(int argc, char *argv[]) {

int values[] = { 80, 50, 70, 10, 60, 20, 40, 30 };

printf("Before QuickSort\n");

printArray(values, 8);

quickSort(values, 0, 7);

printf("\nAfter Sort\n");

printArray(values, 8);

return 0;

}

C Selection Sort로 오름차순 정렬하는 방식입니다.

시간복잡도 : O(n^2)

#include <stdio.h>

void printArray(int value[], int count) {

int i = 0;

for (i = 0; i < count; i++) {

printf("%d ", value[i]);

}

printf("\n");

}

void selectionSort(int value[], int count) {

int i = 0, j = 0, min = 0, temp = 0;

for (i = 0; i < count - 1; i++) {

min = i;

for (j = i + 1; j < count; j++) {

if (value[j] < value[min]) {

min = j;

}

}

temp = value[i];

value[i] = value[min];

value[min] = temp;

printf("Step-%d, ", i + 1);

printArray(value, count);

}

}

int main(int argc, char *argv[]) {

int values[] = { 80, 50, 70, 10, 60, 20, 40, 30 };

printf("Before Selction\n");

printArray(values, 8);

selectionSort(values, 8);

printf("\nAfter Sort\n");

printArray(values, 8);

return 0;

}

C Insertion Sort로 오름차순 정렬하는 방식입니다.

시간복잡도 : O(n^2)

#include <stdio.h>

void printArray(int value[], int count) {

int i = 0;

for (i = 0; i < count; i++) {

printf("%d ", value[i]);

}

printf("\n");

}

void insertionSort(int value[], int count) {

int i = 0, j = 0, temp = 0;

for (i = 1; i < count; i++) {

temp = value[i];

j = i;

while ((j > 0) && value[j - 1] > temp) {

value[j] = value[j - 1];

j = j - 1;

}

value[j] = temp;

printf("Step-%d,", i);

printArray(value, count);

}

}

int main(int argc, char *argv[]) {

int values[] = { 80, 50, 70, 10, 60, 20, 40, 30 };

printf("Before InsertionSort\n");

printArray(values, 8);

insertionSort(values, 8);

printf("\nAfter Sort\n");

printArray(values, 8);

return 0;

}

C Bubble Sort로 오름차순 정렬하는 방식입니다.

시간복잡도 : O(n^2)

#include <stdio.h>

void printArray(int value[], int count) {

int i = 0;

for (i = 0; i < count; i++) {

printf("%d ", value[i]);

}

printf("\n");

}

void bubbleSort(int value[], int count) {

int i = 0, j = 0, temp = 0;

for (i = count - 1; i >= 0; i--) {

for (j = 0; j <= i; j++) { // i 뒤쪽은 다 정렬이 된 자료들이 남아있게 되므로, j <= i 가 된다.

if (value[j - 1] > value[j]) {

temp = value[j - 1];

value[j - 1] = value[j];

value[j] = temp;

}

}

printf("Step-%d, ", count - i);

printArray(value, count);

}

}

int main(int argc, char *argv[]) {

int values[] = { 80, 50, 70, 10, 60, 20, 40, 30 };

printf("Before BubbleSort\n");

printArray(values, 8);

bubbleSort(values, 8);

printf("\nAfter Sort\n");

printArray(values, 8);

return 0;

}

Circular list를 이용하여 List에 데이터를 넣었다가 빼고, 리스트에 존재하는지 등에 대한 Function들을 작성해보았습니다.

(비교, 단일 LinkedList 사용하기 : http://jwprogramming.tistory.com/230 , 

DoubleLinkedList 사용하기 : http://jwprogramming.tistory.com/232 )

(1) circularlistMain.c

#include <stdio.h>

#include <stdlib.h>

#include "Circularlist.h"

int main(int argc, char* argv[]) {

int i = 0;

int arrayCount = 0;

CircularList * pList = NULL;

CircularListNode * pNode = NULL;

CircularListNode node;

pList = createCircularList();

if (pList != NULL) {

node.data = 1;

addCLElement(pList, 0, node);

node.data = 3;

addCLElement(pList, 1, node);

node.data = 5;

addCLElement(pList, 2, node);

displayCircularList(pList);

removeCLElement(pList, 0);

displayCircularList(pList);

deleteCircularList(pList);

}

return 0;

}

(2) circularlist.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "circularlist.h"

int addCLElement(CircularList* pList, int position, CircularListNode element) {

int ret = FALSE;

int i = 0;

CircularListNode *pPreNode = NULL, *pNewNode = NULL, *pLastNode = NULL;

if (pList != NULL) {

if (position >= 0 && position <= pList->currentElementCount) {

pNewNode = (CircularListNode*)malloc(sizeof(CircularListNode));

if (pNewNode == NULL) {

printf("오류, 메모리할당 addLLElement() \n");

return ret;

}

*pNewNode = element;

pNewNode->pLink = NULL;

if (position == 0) {

if (pList->currentElementCount == 0) {

pList->pLink = pNewNode;

pNewNode->pLink = pNewNode;

}

else {

pLastNode = pList->pLink;

while (pLastNode->pLink != pList->pLink) {

pLastNode = pLastNode->pLink;

}

pList->pLink = pNewNode;

pNewNode->pLink = pLastNode->pLink;

pLastNode->pLink = pNewNode;

}

}

else {

pPreNode = pList->pLink;

for (i = 0; i < position - 1; i++) {

pPreNode = pPreNode->pLink;

}

pNewNode->pLink = pPreNode->pLink;

pPreNode->pLink = pNewNode;

}

pList->currentElementCount++;

ret = TRUE;

}

else {

printf("오류, 위치 인덱스-[%d], addCLElement() \n", position);

}

}

return ret;

}

int removeCLElement(CircularList* pList, int position) {

int ret = FALSE;

int i = 0, arrayCount = 0;

CircularListNode *pPreNode = NULL, *pDelNode = NULL, *pLastNode = NULL;

if (pList != NULL) {

arrayCount = getCircularListLength(pList);

if (position >= 0 && position < arrayCount) {

if (position == 0) {

pDelNode = pList->pLink;

if (arrayCount == 1) {

free(pDelNode);

pList->pLink = NULL;

}

else {

pLastNode = pList->pLink;

while (pLastNode->pLink != pList->pLink) {

pLastNode = pLastNode->pLink;

}

pLastNode->pLink = pDelNode->pLink;

pList->pLink = pDelNode->pLink;

free(pDelNode);

}

}

else {

pPreNode = pList->pLink;

for (i = 0; i < position - 1; i++) {

pPreNode = pPreNode->pLink;

}

pDelNode = pPreNode->pLink;

pPreNode = pDelNode->pLink;

free(pDelNode);

}

pList->currentElementCount--;

ret = TRUE;

}

else {

printf("오류, 위치 인덱스-[%d] removeCLElement() \n", position);

}

}

return ret;

}

CircularListNode* getCLElement(CircularList* pList, int position) {

int i = 0;

CircularListNode* pNode = NULL;

if (pList != NULL) {

if (position >= 0 && position < pList->currentElementCount) {

pNode = pList->pLink;

for (i = 0; i <= position; i++) {

pNode = pNode->pLink;

}

}

}

return pNode;

}

CircularList* createCircularList() {

CircularList *pReturn = NULL;

int i = 0;

pReturn = (CircularList *)malloc(sizeof(CircularList));

if (pReturn != NULL) {

memset(pReturn, 0, sizeof(CircularList));

}

else {

printf("오류, 메모리할당 createCircularList()\n");

return NULL;

}

return pReturn;

}

void displayCircularList(CircularList* pList) {

int i = 0;

if (pList != NULL) {

printf("현재 원소 개수: %d\n", pList->currentElementCount);

for (i = 0; i < pList->currentElementCount; i++) {

printf("[%d], %d\n", i, getCLElement(pList, i)->data);

}

}

else {

printf("원소가 없습니다.\n");

}

}

int getCircularListLength(CircularList* pList) {

int ret = 0;

if (pList != NULL) {

ret = pList->currentElementCount;

}

return ret;

}

void deleteCircularList(CircularList* pList) {

int i = 0;

if (pList != NULL) {

clearCircularList(pList);

free(pList);

}

}

void clearCircularList(CircularList* pList) {

if (pList != NULL) {

if (pList->currentElementCount > 0) {

removeCLElement(pList, 0);

}

}

}

(3) circularlist.h

#ifndef _CIRCULARLIST_

#define _CIRCULARLIST_

typedef struct CircularListNodeType

{

int data;

struct CircularListNodeType* pLink;

} CircularListNode;

typedef struct CircularListType

{

int currentElementCount;

CircularListNode* pLink;

} CircularList;

void displayCircularList(CircularList* pList);

CircularList* createCircularList();

int addCLElement(CircularList* pList, int position, CircularListNode element);

int removeCLElement(CircularList* pList, int position);

void deleteCircularList(CircularList* pList);

void clearCircularList(CircularList* pList);

int getCircularListLength(CircularList* pList);

#endif

#ifndef _COMMON_LIST_DEF_

#define _COMMON_LIST_DEF_

#define TRUE 1

#define FALSE 0

#endif