선택정렬 알고리즘(Selection sort)

선택정렬 알고리즘(Selection sort)

선택정렬 알고리즘에 대해서 설명하겠습니다.

선택정렬 알고리즘이란?? 

< 출처 : 컴퓨터인터넷IT용어대사전 >

그림으로 보면 이렇다.

그림으로 보면은 정렬할 값을 콕 찝어서 정렬을 하는거 같지만

우리가 코드로 나타내면 하나하나 일일이 다 값을 비교를 해봐야 한다.

그래야 정렬이 되니까.

그럼 바로 코드를 보자

#include <iostream>
using namespace std;
void printArray(const int array[], const int length)
{
    for (int index = 0; index < length; index++)
        cout << array[index] << " ";
    cout << endl;
}
void sort(int array[], const int length)
{
    bool flag = false;
    for (int i = 0; i < length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < length; j++) {
            if (array[min] > array[j]) {
                min = j;
                flag = true;
            }
        }
        if (flag) { // std::swap(array[min], array[i]); 
            int temp = array[min];
            array[min] = array[i];
            array[i] = temp;
        }
        printArray(array, length);
        flag = false;
    }
}
int main()
{
    const int length = 5;
    int array[length] = { 3,5,2,1,4 };
    printArray(array, length); // sort before print
    sort(array, length);
}

< 출력 >

11행부터 바로 보자.

bool 타입으로 false 값을 넣어놨다. 그 이유는 만약 정렬이 이미 된 상태로 선택정렬을 하면??

쓸때 없이 시간을 허비하면서 21~23행을 실행하게 될것이다.(현재는 작은 값이기에 별 상관은 없지만 엄청 큰 배열이면 많은 리소스가 예상된다.)

12행에서 보면 조건값이 length - 1로 해놨다 그 이유는 14행 j 에서 i + 1번째 배열을 보기 때문이다.

12행에서 조건값이 length라면 i 값이 4일때 j는 5번째 배열을 보게 될 것이다. 그럼 메모리 침범으로 오류가 나게 될 것이다.

13행에서 작은 값을 넣어 놓기 위해 min 변수에 i 값을 넣어 놓았다.

16행에서 만약 array[min] > array[j] 이면 작은 값의 index를 min에다가 보관하고 flag를 true로 바꿔준다.

20행에서 std::swap 대체가 가능하다.

그리고 다시 26행에서 flag를 false로 만들어준다.

이렇게하면 선택정렬이 완성이 됬다.