[C++] 탐색 - 순차 탐색(Sequential Search)

- 순차 탐색 sequential search이란 순서대로 찾아간다는 의미이다.

배열은 메모리가 1차원 직선으로 나열된 형태라 선형(linear)이라는 용어를 사용하는 경우가 많은데,

배열을 순차적으로 탐색하는 것은 메모리를 한 칸 한 칸 선형으로 찾는 것이므로 선형 탐색이라고도 부른다.

#include <iostream>
using namespace std;

void Print(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		cout << arr[i] << ' ';
	}
	cout << '\n';
}

int Count(int* arr, int size, int k)
{
	int count = 0;
	for (int i = 0; i < size; i++)
	{
		if (k == arr[i])
			count++;
	}

	return count;
}

int SequentialSearch(int* arr, int size, int k)
{
	int index = -1;
	for (int i = 0; i < size; i++)
	{
		if (k == arr[i])
		{
			index = i;
			return index;
		}
	}

	/*
	int i;
	for (i = 0; i < size && k != arr[i]; i++);

	if (i == size)
		return -1;
	else
		return i;
		*/

	return index;
}

void InsertionSort(int* arr, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		if (arr[i] > arr[i + 1])
		{
			int insertNum = arr[i + 1];
			int insertIndex = -1;
			for (int j = i; j >= 0 && insertNum < arr[j]; j--)
			{
				arr[j + 1] = arr[j];
				insertIndex = j;
			}
			arr[insertIndex] = insertNum;
		}
	}
}

int SortedCountHelper(int* arr, int size, int k, int start)
{
	int sortCount = 0;
	for (int i = start; k == arr[i]; i++)
	{
		sortCount++;
	}
	return sortCount;
}

int SortedCount(int* arr, int size, int k)
{
	int i = SequentialSearch(arr, size, k);

	if (i < 0)
		return 0;
	else
		return SortedCountHelper(arr, size, k, i + 1) + 1;
	// sequentialSearch로 어차피 숫자를 찾았으니까 +1 해두고
	// 효율적으로 (i + 1)번째부터 숫자를 찾게 한다.
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int arr[] = { 8,1,1,3,2,5,1,2,1,1 };
	int n = sizeof(arr) / sizeof(arr[0]);

	cout << "Count 9 = " << Count(arr, n, 9) << '\n';
	cout << "Count 2 = " << Count(arr, n, 2) << '\n';
	cout << "Count 8 = " << Count(arr, n, 8) << '\n';
	cout << "Count 1 = " << Count(arr, n, 1) << '\n';
	cout << '\n';

	cout << "Search 2 = " << SequentialSearch(arr, n, 2) << '\n';
	cout << "Search 5 = " << SequentialSearch(arr, n, 5) << '\n';
	cout << "Search 9 = " << SequentialSearch(arr, n, 9) << '\n';
	cout << '\n';

	InsertionSort(arr, n);

	Print(arr, n);

	cout << "Sorted Count 9 = " << SortedCount(arr, n, 9) << '\n';
	cout << "Sorted Count 2 = " << SortedCount(arr, n, 2) << '\n';
	cout << "Sorted Count 8 = " << SortedCount(arr, n, 8) << '\n';
	cout << "Sorted Count 1 = " << SortedCount(arr, n, 1) << '\n';

	return 0;
}