[Algorithm] 순차 탐색 (Sequential Search)

I. 순차 탐색 (Sequential Search)의 개요

가. 순차 탐색의 정의

• 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법

 

나. 순차 탐색의 종류

• 전진 이동법 (Move To Front): 탐색된 데이터는 가장 앞으로 이동
• 전위법 (Transpose): 바로 앞 데이터와 탐색된 데이터의 위치 변경
• 계수법 (Frequency Count): 데이터마다 탐색된 횟수를 새로 저장하며, 그 횟수를 내림차순 정렬

 

Ⅱ. 순차 탐색의 종류 및 사례

가. 전진 이동법

 

단계	구현 사례
	LinkedList* FindDataMove( LinkedList* Node, int Data) { LinkedList* List = Node; LinkedList* Previous = NULL; while(List != NULL){ if(List->Data == Data){ if(Previous == NULL){ Node = List; } else{ Previous->NextNode = List->NextNode; List->NextNode = Node; Node = List; } break; } Previous = List; List = List ->NextNode; } return node; }

 

나. 전위법

 

단계

구현 사례

LinkedList* FindDataTranspose( LinkedList* Node, int Data) { LinkedList* List = Node; LinkedList* Previous = NULL; LinkedList* Previous_p = NULL; while(List != NULL){ if(List->Data == Data){ if(Previous_p != NULL) Previous_p->NextNode = List; else break; if(Previous != NULL) Previous->NextNode = List->NextNode; List->NextNode = Previous; } else break; } if(Previous != NULL) Previous_p = Previous Previous = List; List = List ->NextNode; }

 

다. 계수법

 

단계	구현 사례
	- 데이터 집합내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장해 두고, 탐색된 횟수가 높은 순으로 데이터 집합을 재구성하는 전략의 알고리즘 - 계수 결과를 저장하는 별도의 공간을 유지해야 하고 계수 결과에 따라 데이터 집합을 재배치해야 한다.