선택정렬

선택정렬

가장 작은 수를 선택하여 앞으로 보내는 정렬법

 

크기가 N인 배열에서의 선택정렬은 가장 작은 수를 찾는 행위를 N번 하게됩니다.

0번 인덱스에 들어갈 가장 작은 수를 1 ~ N번 인덱스에서 찾아서 넣고

1번 인덱스에 들어갈 가장 작은 수를 2 ~ N번 인덱스에서 찾아서 넣고

2번 인덱스에 들어갈 가장 작은 수를 3 ~ N번 인덱스에서 찾아서 넣고

N - 1번 인덱스에 들어갈 가장 작은 수를 N번 인덱스에서 찾아서 넣고

....

 

#include <iostream>

using namespace std;

int arr[1001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	for (int i = 0; i < N - 1; i++)
	{
		// i번째에 들어갈 작은 수를 찾음
		// i ~ N - 1 까지
		int min = i;

		// i + 1 ~ N 까지의 수 중 가장 작은 수 선별
		for (int j = i + 1; j < N; j++)
		{
			if (arr[j] < arr[min])
				min = j;
		}

		// 위치 바꾸기
		int temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
	}

	for (int i = 0; i < N; i++)
		cout << arr[i] << "\n";
	return 0;
}

ㅅ