[알고리즘] 선택정렬

1. 선택정렬 ?

-> 가장 작은 수를 선택하여 교환하고 반복하는 정렬방법
-> 시간 복잡도가 O(N^2)이다.
=> 입력이 많은 정렬의 경우 아주 비효율적임

2. 구현 방법

1.가장 작은 수를 찾는다
2.가장 작은 수와 현재의 인덱스를 교환한다
3.다음 인덱스부터 다시 가장 작은 수를 찾는다
4.반복한다

✍코드

#include <iostream>
using namespace std;
#define n 5
int a[n] = { 5,4,3,2,1 };

void swap(int a[], int minIndex, int i) {
	int temp=a[i];
	a[i] = a[minIndex];
	a[minIndex] = temp;
}

int main() {

	for (int i = 0; i < n ; i++) {
		int minIndex=i; //초기값 설정이 중요!
		for (int j = i; j < n ; j++) {
			if (a[minIndex] > a[j]) {	
				minIndex = j;
			}
		}
		swap(a, minIndex, i);
	}

	for (int i = 0; i < n; i++) {
		cout << a[i]<<'\n';
	}

	return 0;
}