참조의 지역성(locality of reference)에 기반한 검색은 메모리 접근 패턴에 따라 데이터 요소를 재배치하는 기법입니다. 이 프로그램에서는 선형 탐색(linear search) 방식으로 요소를 검색하며, 요소를 찾으면 해당 요소를 배열의 맨 앞으로 이동시킵니다.
이러한 재배치 덕분에 자주 검색되는 항목일수록 배열 앞쪽에 위치하게 되어, 이후 동일한 항목을 다시 검색할 때 더 적은 비교 횟수로 빠르게 찾을 수 있습니다. 이는 'Move-to-Front' 방식의 자기 조직화 리스트(self-organizing list)와 유사한 원리로, 반복적인 검색 요청이 많은 환경에서 성능을 크게 향상시킬 수 있습니다.
알고리즘
Begin
int find(int *intarray, int n, int item)
comparisons = 0으로 초기화
for i = 0 to n-1
comparisons 증가
if(item == intarray[i])
인덱스와 함께 요소 출력
break
if(i == n-1)
요소를 찾지 못했다고 출력
return -1
총 비교 횟수 출력
For j = i till i>0
intarray[j] = intarray[j-1]
intarray[0] = item
return 0
End
예제 코드
#include<iostream>
using namespace std;
// 선형 탐색을 수행하는 함수.
// 이 메소드는 선형 탐색 방식으로 동작합니다.
int find(int *intarray, int n, int item) {
int i;
int comparisons = 0;
// 모든 항목을 순회
for(i = 0;i<n;i++) {
// 수행된 비교 횟수를 카운트
comparisons++;
// 항목을 찾으면 루프 종료
if(item == intarray[i]) {
cout<<"element found at:"<<i<<endl;
break;
}
// 인덱스가 끝에 도달하면 해당 항목이 존재하지 않음.
if(i == n-1) {
cout<<"\nThe element not found.";
return -1;
}
}
printf("Total comparisons made: %d", comparisons);
// 일치한 항목 앞의 모든 요소를 한 칸씩 뒤로 이동.
for(int j = i; j > 0; j--)
intarray[j] = intarray[j-1];
// 최근 검색된 항목을 배열의 맨 앞에 배치.
intarray[0] = item;
return 0;
}
int main() {
int intarray[20]={1,2,3,4,6,7,9,11,12,14,15,16,26,19,33,34,43,45,55,66};
int i,n;
char ch;
// 초기 데이터 배열 출력.
cout<<"\nThe array is: ";
for(i = 0; i < 20;i++)
cout<<intarray[i]<<" ";
up:
cout<<"\nEnter the Element to be searched: ";
cin>>n;
// 갱신된 데이터 배열 출력.
if(find(intarray,20, n) != -1) {
cout<<"\nThe array after searching is: ";
for(i = 0; i <20;i++)
cout<<intarray[i]<<" ";
}
cout<<"\n\nWant to search more.......yes/no(y/n)?";
cin>>ch;
if(ch == 'y' || ch == 'Y')
goto up;
return 0;
}
실행 결과
The array is: 1 2 3 4 6 7 9 11 12 14 15 16 26 19 33 34 43 45 55 66
Enter the Element to be searched: 26
element found at:12
Total comparisons made: 13
The array after searching is: 26 1 2 3 4 6 7 9 11 12 14 15 16 19 33 34 43 45 55 66
Want to search more.......yes/no(y/n)?y
Enter the Element to be searched: 0
The element not found.
Want to search more.......yes/no(y/n)?n
위 실행 결과에서 볼 수 있듯이, 값 26을 검색하면 인덱스 12에서 13번의 비교 끝에 발견되며, 검색 후에는 해당 요소가 배열의 맨 앞(인덱스 0)으로 이동한 것을 확인할 수 있습니다. 만약 같은 값을 다시 검색한다면 단 한 번의 비교만으로 즉시 찾을 수 있게 됩니다.