Aif

퀵 정렬은 분할 정복 알고리즘의 일종이다. 퀵 정렬은 key값을 정하고 key값을 기준으로 왼쪽은 작은 값 오른쪽은 큰 값을 모은 뒤, key값을 알맞은 위치에 삽입하고 이 위치를 기준으로 분할하여 퀵 정렬을 수행한다. 말로만 보면 복잡하여 이해하기가 어렵다. void quickSort(int* arr, int start, int end) { if (start >= end) return; int key = start; int i = start + 1; int j = end; int temp; while (i = arr[i]) i++; while (arr[key]

삽입 정렬은 배열을 최소 단위에서 하나씩 늘려가며 정렬을 실행한다. 배열의 다음 데이터를 확인하고 그 데이터의 알맞은 자리를 찾아 입력하게 된다. 이 과정이 데이터를 꺼내 알맞은 자리에 삽입하는 것처럼 보여 삽입 정렬이다. 삽입 정렬은 버블 정렬과 비슷한 구현 난이도에 비슷한 성능이지만, 장점이 있다. 이미 정렬된 집합의 경우 삽입 정렬이 성능이 월등히 좋아진다. void InsertionSort(int DataSet[], int Length) { int i = 0; int j = 0; int value = 0; for (i = 1; i < Length; i++) { if (DataSet[i - 1] value) { memmove(&DataSet[j + 1], &DataSet[j], sizeof(Data..

버블 정렬은 정렬되는 모습이 거품이 일어나는 듯하다 해서 버블 정렬이다. 버블 정렬은 인접한 데이터와 자신을 비교하여 기준에 따라 정렬하는 것을 무수히 반복하면 된다. 문장에서 '기준'과 '무수히'라는 표현이 애매하게 만드는 것 같다. 기준은 오름차순 정렬을 기준으로 한다. 무수히는 데이터의 개수를 n개라 했을 때 n-1회 반복하면 된다. n-1회는 최악의 경우를 고려하여 계산해 보면 알 수 있다. 버블 정렬은 인접한 데이터와 자신을 비교하여 자신이 크면 바꾸는 것을 n-1회 반복하면 된다. void BubbleSort() { int i = 0; int j = 0; int temp = 0; int DataSet[10] = { 5, 6, 9, 1, 2, 4, 3, 7, 8, 10 }; Length = si..

트리는 연결 리스트의 노드들에 연결 리스트가 여러개가 주렁 주렁 달려 있는 것과 비슷하다고 생각했다. 생각했으면 바로 구현이 가능하다. typedef struct tagNode { int Data; struct tagNode* NextNode; } Node; Node* CreateNode(int NewData) { Node* temp = (Node*)malloc(sizeof(Node)); temp->Data = NewData; temp->NextNode = NULL; return temp; } CreateNode(1)->NextNode[2]; NextNode는 포인터로 선언하였다. 다음과 같이 노드를 생성하고 NextNode의 배열로 입력하는것이 가능하다. 하지만 노드를 추가할 때, 막막해 진다. 그 이..

스택, 큐, 트리는 노드의 관리 방법이라고 할 수 있다. 노드를 추가하고 삭제하는 등의 관리를 할 때, 규칙의 차이를 스택, 큐, 트리라는 이름으로 분류한 것이다. 스택과 큐는 연결 리스트의 기능 중 리스트에 추가, 리스트에서 삭제 만 수정하면 된다. void AppendNode(Node** Head, Node* NewNode) { Node* temp = (*Head); if (temp == NULL) { (*Head) = NewNode; } else { while (temp->NextNode) { temp = temp->NextNode; } temp->NextNode = NewNode; } } void RemoveNode(Node** Head, int Data) { Node* temp = (*Head)..

노드의 데이터 구조 typedef struct tagNode { int Data; Node* NextNode; } Node; 데이터와 다음 노드의 주소가 필요하다. 노드를 이어붙이면 연결 리스트가 된다. 따라서 노드의 생성, 리스트에 추가, 리스트에서 삭제, 노드 검색정도의 기능을 구현해 보았다. Node* CreateNode((void*) NewData) { Node* temp = (Node*)malloc(sizeof(Node)); temp->Data = NewData; temp->NextNode = NULL; return temp; } void AppendNode(Node** Head, Node* NewNode) { Node* temp = (*Head); if (temp == NULL) { (*Hea..

책 - 뇌를 자극하는 알고리즘을 기반으로 내용 정리