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

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

(SingleLinkedList와 비교 : http://jwprogramming.tistory.com/230 )

(CircularList와 비교 : http://jwprogramming.tistory.com/233 )

(1) doublylistMain.c

#include <stdio.h>

#include <stdlib.h>

#include "doublelist.h"

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

int i = 0;

int arrayCount = 0;

DoublyList *pList = NULL;

DoublyListNode *pValue = NULL;

DoublyListNode node = { 0, };

pList = createDoublyList();

if (pList != NULL) {

node.data = 1;

addDLElement(pList, 0, node);

node.data = 3;

addDLElement(pList, 1, node);

node.data = 5;

addDLElement(pList, 2, node);

displayDoublyList(pList);

removeDLElement(pList, 0);

displayDoublyList(pList);

deleteDoublyList(pList);

}

return 0;

}

(2) doublylist.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "doublelist.h"

DoublyList* createDoublyList() {

DoublyList *pReturn = NULL;

int i = 0;

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

if (pReturn != NULL) {

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

pReturn->headerNode.pLLink = &(pReturn->headerNode);

pReturn->headerNode.pRLink = &(pReturn->headerNode);

}

else {

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

return NULL;

}

return pReturn;

}

int addDLElement(DoublyList* pList, int position, DoublyListNode element) {

int ret = FALSE, i = 0;

DoublyListNode *pPreNode = NULL, *pNewNode = NULL, *pTempNode = NULL;

if (pList != NULL) {

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

pNewNode = (DoublyListNode *)malloc(sizeof(DoublyList));

if (pNewNode == NULL) {

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

return ret;

}

*pNewNode = element;

pNewNode->pLLink = NULL;

pNewNode->pRLink = NULL;

pPreNode = &(pList->headerNode);

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

pPreNode = pPreNode->pRLink;

}

pNewNode->pLLink = pPreNode;

pNewNode->pRLink = pPreNode->pRLink;

pPreNode->pRLink = pNewNode;

pNewNode->pRLink->pLLink = pNewNode;

pList->currentElementCount++;

ret = TRUE;

}

else {

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

}

}

return ret;

}

int removeDLElement(DoublyList* pList, int position) {

int ret = FALSE;

int i = 0, arrayCount = 0;

DoublyListNode *pPreNode = NULL, *pDelNode = NULL, *pTempNode = NULL;

if (pList != NULL) {

arrayCount = getDoublyListLength(pList);

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

pPreNode = &(pList->headerNode);

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

pPreNode = pPreNode->pRLink;

}

pDelNode = pPreNode->pRLink;

pPreNode->pRLink = pDelNode->pRLink;

pDelNode->pRLink->pLLink = pPreNode;

free(pDelNode);

pList->currentElementCount--;

ret = TRUE;

}

else {

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

}

}

return ret;

}

DoublyListNode* getDLElement(DoublyList* pList, int position) {

DoublyListNode* pReturn = NULL;

int i = 0;

DoublyListNode* pNode = NULL;

if (pList != NULL) {

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

pNode = pList->headerNode.pRLink;

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

pNode = pNode->pRLink;

}

pReturn = pNode;

}

else {

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

}

}

return pReturn;

}

void displayDoublyList(DoublyList* pList) {

int i = 0;

if (pList != NULL) {

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

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

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

}

}

else {

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

}

}

void deleteDoublyList(DoublyList* pList) {

if (pList != NULL) {

clearDoublyList(pList);

free(pList);

}

}

void clearDoublyList(DoublyList * pList) {

if (pList != NULL) {

while (pList->currentElementCount > 0) {

removeDLElement(pList, 0);

}

}

}

int getDoublyListLength(DoublyList* pList) {

int ret = 0;

if (pList != NULL) {

ret = pList->currentElementCount;

}

return ret;

}

(3) doublelist.h

#ifndef _DOUBLYLIST_

#define _DOUBLYLIST_

typedef struct DoublyListNodeType {

int data;

struct DoublyListNodeType* pLLink;

struct DoublyListNodeType* pRLink;

} DoublyListNode;

typedef struct DoublyListType {

int currentElementCount;

DoublyListNode headerNode;

} DoublyList;

DoublyList* createDoublyList();

int addDLElement(DoublyList* pList, int position, DoublyListNode element);

int removeDLElement(DoublyList* pList, int position);

DoublyListNode* getDLElement(DoublyList* pList, int position);

void displayDoublyList(DoublyList* pList);

void deleteDoublyList(DoublyList* pList);

void clearDoublyList(DoublyList * pList);

int getDoublyListLength(DoublyList* pList);

#endif

#ifndef _COMMON_LIST_DEF_

#define _COMMON_LIST_DEF_

#define TRUE 1

#define FALSE 0

#endif