[알고리즘] Select Sort (선택정렬)

각 루프마다 최대 원소를 찾는다.

최대 원소와 맨 오른쪽 원소를 교환한다.

맨 오른쪽 원소를 제외하고 탐색

하나의 원소가 남을 때 까지 반복한다.

	<알고리즘>
	selectSort(A[],n){
		for last <- n down to 2{
			A[1 ~ last] 중 가장 큰 수 A[k]를 찾는다;
			A[k] <-> A[last];
		}
	}

<구현>

#include <iostream>
#include <random>
#define SIZE 10
using namespace std;
int A[SIZE];
void print_arr();

void make_num() {
	for (int i = 0; i < SIZE; i++) {
		A[i] = rand() % 10;
	}
	print_arr();
}

void print_arr() {
	for (int i = 0; i < SIZE; i++) {
		cout << A[i] << ' ';
	}
	cout << endl;
}

void select_sort(int n) {
	if (n > 0) {
		int max_temp = 0;
		for (int i = 1; i < n; i++) {
			if (A[i] >= A[max_temp]) max_temp = i;
		}
		int temp = A[n-1];
		A[n - 1] = A[max_temp];
		A[max_temp] = temp;
		select_sort(n - 1);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	/*selectSort [O(n^2)]*/
	make_num();
	select_sort(SIZE);
	print_arr();
	return 0;
}