선택 정렬(Selection Sort)

선택 정렬

선택 정렬은 가장 작은 것부터 선택하여 빼는 방법이다.

#include <iostream>

using namespace std;

bool CheckSorted(int *arr, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        if (arr[i] > arr[i + 1])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    for (int k = 0; k < 3; k++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int i = 0; i < 3; i++)
            {
                int arr[3] = { i, j, k };
                int size = sizeof(arr) / sizeof(int);

                for (int e = 0; e < size; e++)
                {
                    cout << arr[e] << " " << flush;
                }

                cout << "-> " << flush;

                // Selection Sort
                for (int l = 0; l < size - 1; l++)
                {
                    int minIndex = l;
                    for (int n = l + 1; n < size; n++)
                    {
                        if (arr[minIndex] > arr[n])
                        {
                            minIndex = n;
                        }    
                    }
                    int temp = arr[l];
                    arr[l] = arr[minIndex];
                    arr[minIndex] = temp;
                }

                for (int e = 0; e < size; e++)
                {
                    cout << arr[e] << " " << flush;
                }
                cout << boolalpha;
                cout << CheckSorted(arr, size);
                cout << endl;
            }
        }
    }

    return 0;
}

가장 작은 숫자의 인덱스를 찾아서 임시 변수 temp에 저장하고 교환하는 방식을 사용하였다.
제일 기본적인 방식이다.

output

0 0 0 -> 0 0 0 true
1 0 0 -> 0 0 1 true
2 0 0 -> 0 0 2 true
0 1 0 -> 0 0 1 true
1 1 0 -> 0 1 1 true
2 1 0 -> 0 1 2 true
0 2 0 -> 0 0 2 true
1 2 0 -> 0 1 2 true
2 2 0 -> 0 2 2 true
0 0 1 -> 0 0 1 true
1 0 1 -> 0 1 1 true
2 0 1 -> 0 1 2 true
0 1 1 -> 0 1 1 true
1 1 1 -> 1 1 1 true
2 1 1 -> 1 1 2 true
0 2 1 -> 0 1 2 true
1 2 1 -> 1 1 2 true
2 2 1 -> 1 2 2 true
0 0 2 -> 0 0 2 true
1 0 2 -> 0 1 2 true
2 0 2 -> 0 2 2 true
0 1 2 -> 0 1 2 true
1 1 2 -> 1 1 2 true
2 1 2 -> 1 2 2 true
0 2 2 -> 0 2 2 true
1 2 2 -> 1 2 2 true
2 2 2 -> 2 2 2 true

---

std::swap 사용

std::swap 함수를 사용하면 임시 변수를 선언할 필요가 없다.
assert 함수는 에러 검출용 코드이다.
assert함수에 걸리게 되면 버그 발생위치, call stack등 여러 정보를 알 수 있게 된다.

#include <iostream>
#include <cassert>

using namespace std;

bool CheckSorted(int *arr, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        if (arr[i] > arr[i + 1])
        {
            return false;
        }
    }
    return true;
}

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

int main()
{
    int arr[] = {8, 3, 2, 5, 1, 1, 2, 5, 8, 9};
    int size = sizeof(arr) / sizeof(int);

    assert(size > 0);

    for (int l = 0; l < size - 1; l++)
    {
        int min_Index = l;
        for (int n = l + 1; n < size; n++)
        {
            if (arr[min_Index] > arr[n])
            {
                min_Index = n;
            }
        }
        Print(arr, size);
        swap(arr[l], arr[min_Index]);



        cout << "-> " << flush;

        Print(arr, size);

        cout << boolalpha;
        cout << CheckSorted(arr, size);
        cout << endl;

        if (CheckSorted(arr, size) == true)
        {
            break;
        }
    }
    return 0;
}

반복 loop를 끝까지 돌지 않고 CheckSorted 함수를 이용하여 정렬이 완료되면 loop를 탈출한다.

output

8 3 2 5 1 1 2 5 8 9 -> 1 3 2 5 8 1 2 5 8 9 false
1 3 2 5 8 1 2 5 8 9 -> 1 1 2 5 8 3 2 5 8 9 false
1 1 2 5 8 3 2 5 8 9 -> 1 1 2 5 8 3 2 5 8 9 false
1 1 2 5 8 3 2 5 8 9 -> 1 1 2 2 8 3 5 5 8 9 false
1 1 2 2 8 3 5 5 8 9 -> 1 1 2 2 3 8 5 5 8 9 false
1 1 2 2 3 8 5 5 8 9 -> 1 1 2 2 3 5 8 5 8 9 false
1 1 2 2 3 5 8 5 8 9 -> 1 1 2 2 3 5 5 8 8 9 true

---

swap횟수 그래프로 나타내기

다음은 비교 정렬 표이다. (출처 : https://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

정렬 알고리즘이 매우 다양한데, 속도가 다르고 장단점이 다르기 때문에 상황에 맞게 효율적인 알고리즘을 사용하여야 한다.
실제로 선택정렬을 예시로 swap을 몇번 하는지 코드를 통해 알아보자.

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ofstream ofile("log.txt");
    for (int size = 0; size < 1000; size++)
    {
        int count = 0;
        int *arr = new int[size];
        for (int s = 0; s < size; s++)
        {
            arr[s] = size - s;
        }

        int min_index;
        for (int i = 0; i < size - 1; i++)
        {
            min_index = i;
            for (int j = i + 1; j < size; j++)
            {
                count++;

                if (arr[j] > arr[min_index])
                {
                    min_index = j;
                }
            }
            swap(arr[i], arr[min_index]);
        }

        ofile << size << ", " << count << endl;

        delete[] arr;
    }
    ofile.close();

    return 0;
}

ofstream(output file stream)은 프로그램의 출력을 파일에다 할 수 있게 해준다.
(헤더파일 : <fstream> )
이 파일을 실행시키면 log.txt파일을 얻을 수 있다. 복사해서 스프레드시트에 그래프로 나타냈더니
다음과 같은 그래프가 나왔다.

배열의 크기가 커질수록 정렬을 하는데 필요한 교환 횟수가 기하급수적으로 늘어나는데, 어쩔수 없는게 아닐까 라고 생각할 수 있지만 더 효율적인 방법이 있을 것이다.
왜 알고리즘이 중요한지는 뒷내용을 공부하면 차차 알게된다.