순차 탐색(Sequential Search)

순차 탐색(Sequential Search)

정렬되어 있지 않은 데이터에 대해 count와 index를 찾아보고,
정렬되어 있는 데이터에도 똑같은 기능을 하는 함수를 만들어 보았다.

#include <iostream>

using namespace std;

void Print(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " " << flush;
    }
    cout << endl;
}

int Count(int *arr, int n, int element) //배열에서 element가 몇번 나왔는지 반환
{
    int count = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] == element)
        {
            count++;
        }
    }
    return count;
}

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

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

int SortedCountHelper(int *arr, int n, int x, int start)
{
    int count = 0;
    for (int i = start; i < n; i++)
    {
        if (arr[i] == x)
        {
            count++;
        }
        else 
            break; // 조기종료. 정렬이 되있기 때문
    }
    return count;
}

int SortedCount(int *arr, int n, int x)
{
    int i = SequentialSearch(arr, n, x); 

    if (i >= 0) // x가 존재한다면 
    //하나를 찾았으니까 1을 더해주고 다음 index부터 또 x를 찾는다.
        return SortedCountHelper(arr, n, x, i + 1) + 1; 
    else
        return 0;
}

int main()
{
    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) << endl;
    cout << "Count 2 = " << Count(arr, n, 2) << endl;
    cout << "Count 8 = " << Count(arr, n, 8) << endl;
    cout << "Count 1 = " << Count(arr, n, 1) << endl;
    cout << endl;

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

    InsertionSort(arr, n);

    Print(arr, n);

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

    return 0;
}

정렬이 되어 있는 데이터는 같은 숫자끼리 모여있기 때문에 한번 원하는 데이터를 찾게되면, 같은 숫자끼리 모여있기 때문에 다음 index의 원소가 x가 아니라면 조기종료를 하여 연산의 효율을 높일수가 있다.

output

Count 9 = 0
Count 2 = 2
Count 8 = 1
Count 1 = 5

Search 2 = 4
Search 5 = 5
Search 9 = -1

1 1 1 1 1 2 2 3 5 8 
Sorted Count 9 = 0
Sorted Count 2 = 2
Sorted Count 8 = 1
Sorted Count 1 = 5