Selection Sort C++ 로 구현하기

 

#include <iostream>
using namespace std;

void my_sort(int a[], int n) {
	int i, j, min, t;
	for (i = 0; i < n-1; i++) {
		min = i;
		for (j = i + 1; j < n; j++) {
			if (a[j] < a[min])
				min = j;
		}
		t = a[i];
		a[i] = a[min];
		a[min] = t;
	}
}

int main() {
	
	int list[10] = {23,11,15,8,17,33,7,14,19,21};
	int i;
		my_sort(list, 10); // 배열 list의 원소 10개를 sort하는 함수
		for (i = 0; i < 10 ; i++)
			cout << list[i] << "\n";
	return 0;
}

 

여기서 핵심은 my_sort에 대한 이해이다. 

우선 selection sort의 원리에 대해 알아보자.

 

23,11,15,8,17,33,7,14,19,21 이렇게 10개의 숫자가 하나의 열에 저장되어 있다고 했을 때

작은 숫자부터 오름차순으로 sorting 하고자 한다. 

 

이것을 컴퓨터로 구현하기 위해 생각해야 할 것은 

1. 가장 작은 수의 위치를 찾는다.

2. 가장 작은 수의 위치와 가장 왼쪽에 있는 수의 위치를 바꿔준다.

3. 이를 9 번 반복한다.

 

가장 작은 수의 위치는 어떻게 찾을까?

우선 가장 왼쪽에 있는 수를 가장 작은 수라고 가정했을 때 

옆에 잇는 숫자를 반복해서 비교하면 된다. 

만약 옆에 있는 숫자가 가장 왼쪽에 있는 수보다 작다면 그 위치값을 변수에 저장한다.

그 뒤에 가장 왼쪽 값과 가장 작은 값을 변경한다,