[알고리즘 개념] 선택 정렬 (selection sort) c++

선택정렬

 

선택정렬 (selection sort)은 제자리 정렬 알고리즘의 하나이다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

이 1,2,3을 계속 반복하는 알고리즘이다.

출처 위키백과

이런식으로 처음엔 첫번째 원소부터 마지막 원소중 최소값을 찾아 배열 맨 앞에 있는 원소와 교환하고

(정렬된 첫번째 원소를 제외한) 두번째 원소부터 마지막 원소중 최소값을 또 찾아 배열 두번쨰 원소와 교환하고

 배열 마지막 원소는 자동으로 정렬되기 때문에 원소 개수 -1 만큼 반복해 주면 된다.

 

 

C++ 로 구현

 

#include<iostream>
using namespace std;
int a[10] = { 3,6,7,1,4,2,9,0,5,8 };

void selection_sort(int a[], int n)
{
	int min;
	int tmp, index;
	for (int i = 0; i < n-1; i++) {
		min = INT_MAX;  //for문 돌릴때마다 최소값 초기화
		for (int j = i; j < n; j++) {
			if (min > a[j]) {  //최소값 찾기
				min = a[j];
				index = j;
			}
		}
		tmp = a[i];  //현재위치와 최소값과 교환
		a[i] = a[index];
		a[index] = tmp;
	}
}

int main()
{
	selection_sort(a, 10);

	for (int i = 0; i < 10; i++) {
		cout << a[i] << " ";
	}
	return 0;
}