[알고리즘] 선택 정렬(Selection Sort) 알고리즘 쉽게 구현해보기 (C++)

 

 

 

 

이 글은 프로그래밍에 능숙하지 않으신 분들도 어렵지 않게 이해할 수 있도록 최대한 쉽게 풀어 설명한 글입니다.

 

 

 

 

<1> 선택 정렬이란 무엇인가?

 

 

선택 정렬 알고리즘은 기본 정렬 알고리즘 중 하나로

 

다음 아래의 과정을 반복하는 알고리즘이다.

 

 

1. 배열의 주어진 범위에서 최솟값의 위치를 찾는다.

 

2. 최솟값을 해당 범위의 가장 앞 숫자와 자리를 바꾼다.

 

3. 이후, 해당 범위의 가장 앞 자리를 제외한 나머지 범위에 대해 위의 과정을 반복한다.

 

 

위의 과정을 모두 마치면 배열 내 정수의 원소가 오름차순(점점 커지는 순)으로 정렬된다.

 

선택 정렬이 이루어지는 과정을 쉽게 나타낸 그림. 구글링해서 퍼왔다.

 

선택정렬이 이루어지는 과정을 gif로 [출처: https://github.com/GimunLee]

 

 

 

 

<2> 선택 정렬 알고리즘 구현해보기

 

 

먼저, 메인 함수에는 정수형 배열에 원소값을 입력 받고

 

함수로 구현한 알고리즘을 통해 배열 원소를 오름차순으로 재배열 한 후

 

반복문으로 각 원소 값을 출력하는 과정이 있어야 할 것이다.

 

#include <iostream>
using namespace std;

int getMinIndexInRange(int* data, int n, int begin, int end);

void selectionSort(int* data, int n);

int main()
{
  // 필요한 데이터 공간 선언 및 초기화
  int n = 0;  // n : 배열의 원소의 개수
  cin >> n;
  int* data = new int[n];  // 정수형 배열 동적 할당


  // 정수형 배열 각 원소에 입력값 대입
  for (int i = 0; i < n; i++)
  {
    cin >> data[i];
  }
	
    
  // 선택정력 알고리즘 함수를 통해 정수형 배열 오름차순으로 재배열
  selectionSort(data, n);
	
   
  // 배열 원소값 인덱스순으로 출력
  for (int i = 0; i < n; i++)
  {
    if (i > 0)
      cout << " ";
    cout << data[i];
  }

  return 0;
}

 

이제 위에서 설명한 알고리즘의 과정을 한 스텝씩 밟아보며 선택 정렬을 함수로 구현해보자.

 

 

 

 

1. 배열의 주어진 범위에서 최솟값의 위치를 찾는다.

 

 

최솟값의 위치를 찾는 방법은, 배열 내 모든 원소를 순서대로 비교해보고 그 때까지의 최솟값을 계속해서 갱신해 나가는 방법이 있다.

 

그럼 그 최솟값을 저장할 변수가 필요하고

 

배열 내 원소들을 순서대로 탐색해나갈 반복문이 쓰여야 할 것이며

 

탐색의 매 과정마다 현재의 최솟값과 탐색하는 배열 원소의 값을 비교할 떄 필요한 조건문이 반복문 안에 들어가애 할 것이다.

 

int getMinIndexInRange(int* data, int n, int begin, int end)
{
  // 최솟값과 그 위치를 저장할 변수 선언
  // 초기값은 탐색의 첫 번째 원소와 그 인덱스
  // 이를 기준으로 배열의 원소값과 비교해 나갈 것이다.
  int minIndex = begin;
  int minValue = data[begin];

  // 배열을 탐색할 반복문
  for (int i = begin; i < n; i++)
  {	
  	// 매 원소를 현재 최솟값과 비교할 조건문
    if (minValue > data[i])
    {
      minValue = data[i];
      minIndex = i;
    }
    // 반복이 끝나면 minIndex변수에 최솟값의 위치값(인덱스)이 저장되어 있다.
  }
  
  return minIndex;
}

 

 

 

 

2. 최솟값을 해당 범위의 가장 앞 숫자와 자리를 바꾼다.

 

3. 이후, 해당 범위의 가장 앞 자리를 제외한 나머지 범위에 대해 위의 과정을 반복한다.

 

 

두 과정은 묶어서 살펴보자.

 

먼저, 최솟값을 해당 범위의 가장 앞 숫자와 자리를 바꾸는 과정은

 

두 변수의 값을 서로 바꾸는 알고리즘으로 구현 할 수 있다.

 

아마 값에 의한 전달(Call By Value)과 참조에 의한 전달(Call By Reference)을 공부할 때 봤을 매우 간단한 알고리즘이다.

 

void Swap(int a,int b)
{
    int temp = 0;
    
    temp = a;
    a = b;
    b = temp;
}

 

temp라는 임시 변수를 사용하는 방법인데, 이걸 이용해 위에서 구한 배열의 최솟값을 해당 범위의 가장 앞 숫자와 자리를 바꿀 것이다.

 

 

다음과 같이 말이다.

 

void selectionSort(int* data, int n)
{
  // 해당 범위의 가장 앞 자리를 제외한 나머지 범위에 대해 위의 과정을 반복하도록 하는 반복문
  for (int i = 0; i < n-1; i++)
  {
    int minIndex = getMinIndexInRange(data, n, i, n-1);
    int temp = 0;
	
    // 최솟값을 해당 범위의 가장 앞 숫자와 자리를 바꾸는 과정
    temp = data[minIndex];
    data[minIndex] = data[i];
    data[i] = temp;
  }
}

 

 

코드를 보면, 위의 1번 과정을 구현한 getMinIndexInRange함수와 2번 과정인 자리 교체 코드를 반복문 안에 넣음으로써

 

정렬이 끝날 때까지 배열 탐색 및 자리 교체 과정을 계속 반복하도록 하였다.

 

다만, 반복문의 변수 i를 계속 1씩 증가시킴으로 배열의 탐색 시작 위치 또한 1씩 증가한다.

 

 

 

이제 코드를 완성하면 다음과 같다. (주석은 다 뺐다.)

 

#include <iostream>
using namespace std;

int getMinIndexInRange(int* data, int n, int begin, int end)
{
  int minIndex = begin;
  int minValue = data[begin];

  for (int i = begin; i < n; i++)
  {
    if (minValue > data[i])
    {
      minValue = data[i];
      minIndex = i;
    }
  }
  return minIndex;
}

void selectionSort(int* data, int n)
{
  for (int i = 0; i < n-1; i++)
  {
    int minIndex = getMinIndexInRange(data, n, i, n-1);
    int temp = 0;

    temp = data[minIndex];
    data[minIndex] = data[i];
    data[i] = temp;
  }
}

int main()
{
  int n = 0;
  cin >> n;
  int* data = new int[n];

  for (int i = 0; i < n; i++)
  {
    cin >> data[i];
  }

  selectionSort(data, n);

  for (int i = 0; i < n; i++)
  {
    if (i > 0)
      cout << " ";
    cout << data[i];
  }

  return 0;
}

 

 

 

 

<3> 정렬 알고리즘의 시간 복잡도

 

첫 순환의 연산 횟수 = N번

 

두 번째 순환의 연산 횟수 = N-1번

 

...

 

마지막 순환의 연산 횟수 = 1번

 

 

총 연산 횟수 = N + (N-1) + ... + 1 = N(N+1) / 2번

 

시간 복잡도 = O(N^2)

 

 

 

 

 

<4> 마무리

 

필자도 알고리즘 공부를 막 시작한 상태라 자세한 건 아직 잘 모르지만

 

선택 정렬 알고리즘은 단순하고 비교적 많은 교환이 일어나야 하는 자료상태에선 효율적이나

 

시간복잡도 측면에서는 비효율적인 알고리즘이라 한다.