[알고리즘] 선택 정렬(Selection Sort) 알고리즘 쉽게 구현해보기 (C++)
이 글은 프로그래밍에 능숙하지 않으신 분들도 어렵지 않게 이해할 수 있도록 최대한 쉽게 풀어 설명한 글입니다.
<1> 선택 정렬이란 무엇인가?
선택 정렬 알고리즘은 기본 정렬 알고리즘 중 하나로
다음 아래의 과정을 반복하는 알고리즘이다.
1. 배열의 주어진 범위에서 최솟값의 위치를 찾는다.
2. 최솟값을 해당 범위의 가장 앞 숫자와 자리를 바꾼다.
3. 이후, 해당 범위의 가장 앞 자리를 제외한 나머지 범위에 대해 위의 과정을 반복한다.
위의 과정을 모두 마치면 배열 내 정수의 원소가 오름차순(점점 커지는 순)으로 정렬된다.
<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> 마무리
필자도 알고리즘 공부를 막 시작한 상태라 자세한 건 아직 잘 모르지만
선택 정렬 알고리즘은 단순하고 비교적 많은 교환이 일어나야 하는 자료상태에선 효율적이나
시간복잡도 측면에서는 비효율적인 알고리즘이라 한다.