1강 - 선택 정렬 (Selection Sort)

1. 선택 정렬

1) 정의

첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

2) 특징

1> 제자리 정렬 (in-place sorting) -> 다른 추가 메모리를 요구하지 않음

 

2. 구체적인 과정

1> 주어진 array 전체(0~MAX)에서 가장 작은 원소를 찾는다. 

2> '그 작은 원소'와 'array에서 0번째 원소'를 교체한다.

3> 1>~2>를 1번째 원소부터 마지막 원소까지의 범위에서 시행

4> 이를 하나의 원소만 남을 때까지 반복

 

 

3. 구현

1) 기본 구현

#include <iostream>
using namespace std;
const int MAX = 1000;

int main()
{
	int N;
	cin >> N;
	int arr[MAX];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
    
	int min, idx, temp;

	for (int i = 0; i < N; i++)
	{
		min = 9999; // 추후 들어올 수 있는 원소들보다 큰 값으로 min을 설정
		for (int j = i; j < N; j++)
		{
			if (min > arr[j])
			{
				min = arr[j];
				idx = j;
			}
		}
        temp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = temp;
	}
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}

}

1> min을 추후 들어올 어떤 원소보다 크게 잡는다. 

 

cf> swap 함수

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

1> void swap(int &a, int &b){ a..., b,,,)

swap(x, y): 

- 실제 변수(x, y)를 참조할 수 있는 참조자를 호출(함수에 넣는다.)

- 그래서 참조자가 가리키는 값을 swap한다.

 

2> 아래는 같은 말이다.

'void swap(int &a, int &b){ a..., b,,,)' == 'void swap(int *a, int *b){ *a..., *b,,,)'

2) swap 함수를 이용해서 간편하게 구현하기

#include <iostream>
using namespace std;
const int MAX = 1000; // 입력될 수 있는 수의 최댓값

// swap 함수
void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

int main()
{
	// N개의 수를 입력 받았다.
	int N;
	cin >> N;
	int arr[MAX];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
    // 0. 사용할 int 선언
	int min, idx;
	// 1. i번째 자리를 바꿀 것
	for (int i = 0; i < N; i++)
	{
		min = arr[i]; // 일단 정렬 구간의 맨 앞을 min으로 설정
		idx = i; // idx: 최소인 index
        // 2. 조사는 i번째부터 끝(N-1)까지 하고 최솟값을 맨 앞으로 보낸다.
		for (int j = i; j < N; j++)
		{
			if (min > arr[j])
			{
				min = arr[j];
				idx = j;
			}
		}
		swap(arr[i], arr[idx]);
	}
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}
    return 0;
}