C++ 선택정렬 (selection sort)이란 무엇일까? - 대학교 컴공 2학년 자료구조 과목

이 내용은 컴퓨터공학과인 내가 2학년 때 자료구조 과목에서 배우는 내용이다. 고3 때도 배운 적 있는 거 같긴 하다. 막 버블정렬 이런 거 배우면서. 그만큼 기초적인 내용이라는 거겠지? 아아~ 난 퇴화했다~ 아무튼 시작해 보겠다.
 

SelectionSort - 선택정렬의 정의

선택정렬이란 무엇일까? 주어진 배열을 맨 앞부터 쭉 읽어나가 최솟값을 찾아 맨 앞의 배열요소에 위치시키고, 두 번째부터 쭉 읽어나가 읽은 배열요소 중 최솟값을 두 번째에 위치시키고, 세 번째부터 쭉 읽어나가... 를 반복해, 배열요소를 오름차순으로 정렬해 주는 알고리즘이다. 

바로 코드로 가보겠다.

수업 때 나온 선택정렬의 예시코드

void SelectionSort(int* a, const int n)
{
	for (int i = 0; i < n; i++) {
		int j = i;
		for (int k = i + 1; k < n; k++)
			if (a[k] < a[j]) j = k;
		swap(a[i], a[j]);
	}
}

void SelectionSort(int*a, const int n) 설명

void : 보면 반환값이 없는 void 자료형을 사용한다. 목표하는 배열을 수정하는 것이 목표이므로 수정이 끝났을 때 별도의 값을 반환할 필요가 없어서 void를 쓰나 보다.

SelcectionSort라는 함수를 만드는데, 매개변수가 int*a와 const int n이다. int*a는 포인터 형태의 매개변수로, 배열의 첫 번째 값을 나타낸다.

int*a : 메인함수에서 배열을 작성하고, 배열의 이름을 저 매개변수 자리에 넣게 되면 저 포인터 형태가 배열의 첫 번째 값부터 읽을 수 있는 것이다. 그래서 매개변수가 포인터여야 하는 것이다!!

const int n : 배열요소의 개수를 나타내는 것이다. const 선언이 되어있어서 함수 내에서 바뀌지 않고 고정된 상수 값이다. 어차피 건드릴 일이 없지만 GPT 씨한테 물어보니까 의도의 명확성 때문에 상수선언을 한단다. 바뀌면 안 되는 값이기는 하지 않은가?

구조 설명

SelctionSort 함수는 두 개의 for 반복문으로 구성되어 있다.

첫 번째 반복문은 i를 인자로 돌아간다. 배열의 요소를 0부터 n-1번째까지 주르륵 훑기 위해 존재한다.

두 번째 반복문은 그리고 k와 j를 인자로 돌아간다. 이는 i+1번째 배열요소를 그 후의 배열요소들과 모두 비교하며, i+1번째 배열요소보다 작을 경우 그 둘을 swap 하고, 그렇지 않을 경우엔 다음 배열요소로 넘어간다. 배열의 맨 끝요소까지 진행한 후에는 첫 번째 반복문으로 나간다. 

지역변수의 존재이유 설명

i : 지역변수 i는 배열요소를 첫 번째부터 마지막까지 특정하기 위한 변수이다.

k : 두 번째 반복문 내에서 시작 위치에서 끝까지 훑는 역할인 지역변수이다.

j :
 j는, 두 번째 반복문 내부로 들어갔을 때, 현재 위치해 있는 배열요소 순서인 i 값을 활용해야 하는데, 활용함에 따라 i의 값이 바뀌면 안 되므로 int j =i; 로 j에  i값을 할당해 준 후 두 번째 반복문에서 그 값을 사용하는 것이다.

if (a [k] < a [j]) j = k; 에서 볼 수 있듯이, 두 번째 반복문 안에서 a [k]가 시작 위치인 a [j]보다 작을 경우에 j에 k 값을 대입하여 a [j]를 시작위치인 a [i]와 swap 한다.

쓰다 보니 든 의문 :  j가 왜 필요한 거지? 없어도 잘 돌아갈 거 같은데?

//선택정렬

#include<iostream>
using namespace std;

void SelectionSort(int* a, const int n) {
	for (int i = 0; i < n; i++) {
		for (int k = i + 1; k < n; k++) {
			if (a[k] < a[i]) swap(a[k], a[i]);
		}
	}
}


int main() {
	int num[] = { 5,3,4,1,2 };
	int size = 5;

	SelectionSort(num, size);

	for (int i = 0; i<size; i++) {
		cout << num[i] << " ";
	}
	cout << endl;
	return 0;
}

내가 작성해 본 코드다. 잘만 돌아가는데? j는 어디 필요한 거지? 근데 피곤해서 이만 줄인다. 혹시 이 글을 읽은 사람 중에 지역변수 j가 왜 필요한지 아는 사람은 설명 좀 부탁해요