ETC/Data Struct | Algorithm

정렬 - 퀵 정렬(Quick Sort)

퀵 정렬은 많이 사용되는 정렬 중 하나이다. 퀵 정렬은 임의의 Pivot 값을 선정하고 Pivot값보다 큰 값과 작은 값을 나눠 정렬하는 방식이다. 오름차순을 이용하여 설명하면, 먼저, 외쪽에서 오른쪽으로 피봇값보다 큰 값을 찾을 때까지 우측으로 이동하고, 다음, 오른쪽에서 왼쪽으로 피봇보다 작은 값을 찾을때까지 좌측으로 이동하여, 처음 발견되는 값들을 서로 Swap한다. 그런 과정을 지속적으로 반복하여 정렬하여 준다. 내림차순은 조건을 반대로 해줌으로써 할 수 있다. 퀵 정렬은 재귀호출을 사용하여 이용함으로써 간편하게 해답을 찾을 수 있다. Quick_Sort. #ifdef _QUICK_SORT_ #endif _QUICK_SORT_ //오름차순 void Asc_Quick_Sort(int data[], ..

정렬 - 버블 정렬 (Bubble_Sort)

버블 정렬은 정렬되지 않은 데이터에 대하여 인접한 두개의 데이터를 지속적으로 비교해 나가며 정렬하는 방식이다. 첫번째 인덱스부터 시작하여 오름,또는 내림으로 정렬할 시 인접한 두번째 인덱스의 자료와 비교하여 교환하고 비교해 나가면서 정렬한다. 오름차순과 내림차순의 차이는 조건의 차이 하나밖에 없으므로 동일하다고 보면 된다. 아래 소스는 버블 정렬에 대한 헤더파일과 소스파일이다. Bubble_Sort.h#ifdef _BUBBLE_SORT_ #endif _BUBBLE_SORT_ void Asc_Bubble_Sort(int data[], int size); //오름차순 void Des_Bubble_Sort(int data[], int size); //내림차순 void Prt_Bubble_Sort(int dat..

정렬 - 선택 정렬 (Selection Sort)

선택 정렬은 정렬되지 않은 전체 자료들을 하나씩 비교해 가며 위치를 교환하여 정렬하는 방식이다. 가장 간단한 정렬방식이지만, 효율성은 그렇게 높지 않다. 그러므로 큰 데이터에서 사용하는 것은 좋지 않다. 아래 코드는 오름차순 정렬과 내림차순 정렬, 그리고 정렬된 데이터를 출력하는 함수로 이루어진 헤더파일과 소스파일입니다. main문이 없으므로, 참조바랍니다. Selection_Sort.h #ifdef _SELECTION_SORT_ #endif _SELECTION_SORT #ifdef _SELECTION_SORT_ #endif _SELECTION_SORT void Ascending_Sort(int data[], int size); //오름차순 정렬 void Descending_Sort(int data[],..

연결리스트 (LinkedList)

연결리스트(LinkedList)는 자료구조의 가장 기초적인 자료구조이다. 데이터를 저장하기 위한 선형구조로써 데이터간 1:1로 대응하고 있다. 연결리스트는 크게 데이터와 다음 List를 가리키는 포인터로 이루어져 있다고 생각하면 된다. 위 그림 처럼 연결..... 되어 있다고 생각하면 된다. 먼저 노드를 삽입하기 위해서는 위 순서대로 새로운 노드가 삽입하기 위한 위치의 노드를 가리키고 이전노드가 새로운 노드를 가리키게 됩니다. 다음 노드를 삭제하기 위해서는 이전의 노드가 삭제 하려는 노드가 가리키던 노드를 가리키고... 음...... 제일 첫 번째 노드부터 1, 2, 3번 노드 라 하면 기존에는 1->2, 2->3으로 되어있던 리스트를 1->3으로 변경한 후 2번 노드를 삭제하면 됩니다. 소스코드는 헤더..

순차 검색

순차 검색은 데이터를 검색하기 위한 가장 기초적인 검색 방법 하나 이다. 1. 자료가 미리 정렬되지 않은 경우의 순차 검색 - 모든 자료를 처음부터 마지막까지 순차적으로 모두 비교하며 검색한다. 그러므로 데이터가 자료에 있는지 없는지 여부는 검색을 마지막까지 모두 검색한 후에나 확인 가능하다. 2. 자료가 미리 정렬된 경우의 순차 검색 - 이 경우도 위와 동일하게 처음부터 마지막까지 순차적으로 모두 비교하며 검색한다. 하지만 위의 경우와는 다르게 데이터가 정렬되 있으므로, 자료가 조건에 만족하지 못한다면, 중간에 데이터 유무를 확인할 수 있다. 3. 색인 순차 검색 색인 순차 검색은 자료의 Index를 가지고 검색하는 방식으로 기존의 데이터의 Index에 해당하는 데이터를 가지고 검색하므로 검색의 효율을..