정렬(Sort) : 선택정렬(Selection Sort)

이번 글은 자료구조 두번째 포스팅으로 선택정렬에 대하여 다루어 보겠다.

이전 게시글 )

정렬(Sort) : 삽입정렬(Insertion Sort) : http://andrew0409.tistory.com/138

파이썬 예제 : 리스트를 정렬(Sort)하는 여러가지 방법 : http://andrew0409.tistory.com/65

파이썬 예제 : 튜플(Tuple)을 정렬(Sort)하는 여러가지 방법 : http://andrew0409.tistory.com/66

                     

참고용으로 올린 위 그림은 선택정렬의 알고리즘을 그림으로 표현한것입니다.

이전 포스팅인 삽입정렬에서 설명이 조금 부족했다는 생각에 덧붙이자면, 삽입정렬은 배열 내 "정렬된 부분" 과 "정렬되지 않은 부분"이 있을때 정렬되지 않은 부분에서 가장 작은 숫자를 정렬된 부분에 "삽입"하면서 정렬된부분을 한칸씩 옆으로 밀어 영역을 넓이는 방법이고, 선택정렬은 마찬가지로 정렬되지 않은 부분에서 가장 작은 숫자를 찾지만, 옆으로 한칸씩 밀어 삽입하는 방법이 아닌, 자리를 바꿔서 정령하는 방법입니다. 얼핏 보면 비슷한 알고리즘이지만 삽입정렬은 데이터를 중간에 삽입하는 방법이고 선택정렬은 자리를 바꿔버리는 방법이라는 점에서 그 차이점을 찾을 수 있습니다.

바로 코드를 살펴보도록 하지요. 두개의 함수를 정의하여 사용하겠습니다. 

int findMaxPos(int *p, int size)
{
    int pos = 0;
    for (int i = 1; i <size; i++)
    {
        if (p[pos] < p[i])
            pos = i;
    }
 
    return pos;
}
 
void selectionSort(int *p)
{
    int temp;
    int size = ARRAY_SIZE;
 
    for (size; size> 1; size--)
    {
        temp = findMaxPos(p, size);
        std::swap(p[temp], p[size - 1]);
    }
}

배열에서 가장 큰 숫자의 위치를 찾는 findMaxPos와 selectionSort를 정의하였습니다. 한번 살펴보도록 하겠습니다.

셀렉션 소트 함수 중간에 std::swap 이라는 함수를 사용하였는데요. 다음에 std에 관한 포스팅을 하면 자세히 언급하겠습니다만, 이번 포스팅에서는 간단한 설명만 하고 넘어가도록 하겠습니다. 일반적으로 변수 a와 b의 내용을 바꿀때는 아래와 같이 사용하곤 합니다.

int a = 10 ,b = 20 ,temp;
 
temp = a;
a = b;
b = temp;

std::swap(a,b);

std를 사용하여 한줄로 끝냈습니다. 헤더는 #include <algorithm> 을 사용하시면 되겠습니다. 아무튼 양 변수를 스왑해주는 것일뿐 큰 의미는 없습니다. 본론으로 돌아가서 계속하겠습니다.

반복문을 보시면 가장 큰 방의 번호(10) 부터 시작하여 1까지 줄어들며 배열의 오른쪽부터 차차 정렬하는 식입니다. 한번 흐름을 타고 쫓아가보겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define ARRAY_SIZE 10
 
int findMaxPos(int *p, int size);
void selectionSort(int *p);
 
int main()
{
    int size = ARRAY_SIZE;
    int arr[10];
 
    for (int i = 0; i < size; i++)
        arr[i] = rand() % size + 10;
 
    selectionSort(arr);
 
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    return 0;
}

메인 소스코드입니다. 참고하시구요. 셀렉션 소트 함수 사용 전까지는 배열의 선언, 초기화 과정이고 아래는 출력과정입니다.

선언한 방 10개짜리의 배열을 셀렉션소트로 보냅니다. 앞 포스팅에서 이야기 했지만 "배열의 이름은 곧 그 배열의 시작주소 상수값"입니다. 따라서 int의 포인터형 되겠지요.

셀렉션 소트에서는 배열을 전달인자로 받고, 임시변수인 temp를 선언, size를 선언합니다. 매크로 상수를 사용했습니다.

핵심이 되는 반복문입니다. findMaxPos 함수를 통해 가장 큰 숫자의 방번호를 찾을 수 있습니다. findMaxPos는 가장 큰 "값"을 찾는것이 아니라 "값의 방 번호"를 찾는 함수입니다. 착오없으시길, 아무튼 찾은 방의 번호를 임시변수인 temp에 저장합니다. 그리고 p[temp]와 p[size-1]을 스왑합니다. 이렇게 하면 배열내에서 가장 큰 숫자가 가장 오른쪽으로 가며, 오른쪽부터 "정렬된 상태"가 됩니다. 반복문이 계속되면서 size를 하나씩 줄여가며 정렬된 부분과 정렬되지 않은 부분을 구분합니다.

처음에 언급했듯이, 삽입정렬과 선택정렬은 얼핏 보면 비슷해보이지만, 삽입정렬은 한칸씩 옆으로 당겨서 자리에 낑겨 들어가는 식이고, 선택정렬은 그냥 값을 바로 스왑해버리는 점이 다른 점입니다.

이 글을 보시는 여러분께 도움이 되셨으면 하고, 잘 이해가 안되거나 설명이 부족한 부분에 대해서 질문 하시면 친절히 답변 드리겠습니다. 지적도 달게 받습니다. 댓글과 추천은 큰 힘이 됩니다. 감사합니다.