[간단하게] 정렬 알고리즘 c++ (선택 알고리즘)

선택 알고리즘을 아주 간단하게 알아보겠다.

정렬 알고리즘중 가장 기본인 선택 정렬이다.

int arr[6] = { 6, 2, 4, 9, 1, 2 };

6

2

4

9

1

2

위의 배열이 있다고 가정하고 선택 정렬을 해보자. 배열은 오름차순으로 정렬할것이다.

for (int i = 0; i < 6; i++) {
	int idx = i, min = arr[i];

배열 전체를 도는 반복문을 하나 설정한다.

int idx는 위치를 바꿀 배열의 위치, min은 현재 선택된 가장 작은 배열이다.

처음에는 idx는 i로 min은 ar[i]로 초기화해놓는다.

	for (int j = i; j < 6; j++) {
		if (min > arr[j]) {
			min = arr[j];
			idx = j;
		}
	}

i를 포함한 i뒤의 배열 전체를 돌며 만약 현재 선택된 가장 작은 배열보다 더 작은 배열이 있다면

min을 더 작은 배열로 업데이트 한뒤 idx를 더 작은 배열의 위치로 바꾼다.

6

2

4

9

1

2

위의 배열을 예로 들자. 현재 idx는 0이고 min은 6이다.

6

2

4

9

1

2

뒤의 배열을 하나하나 살피며 min보다 작은 배열을 찾는다.

2가 min보다 작으니 idx를 1로, min을 2로 바꾼다.

6

2

4

9

1

2

배열을 전부 돌면 idx은 4, min은 1인 상태가 된다.

	swap(arr[i], arr[idx]);
}

i와 idx의 배열 값을 교체해준다.

1

2

4

9

6

2

이 과정을 끝까지 반복해주면 된다.

1

2

4

9

6

2

2번째에서는 2보다 작은 수가 없으니 바꿀 필요는 없다.

1

2

2

9

6

4

1

2

2

4

6

9

1

2

2

4

6

9

1

2

2

4

6

9

모든 과정을 반복하면 오름차순으로 배열이 정렬된다.

#include <iostream>

using namespace std;

int main()
{
	int arr[6] = { 6, 2, 4, 9, 1, 2 };
	for (int i = 0; i < 6; i++) {
		int idx = i, min = arr[i];
		for (int j = i; j < 6; j++) {
			if (min > arr[j]) {
				min = arr[j];
				idx = j;
			}
		}
		swap(arr[i], arr[idx]);
	}
	for (int i = 0; i < 6; i++) cout << arr[i] << ' ';
}

시간복잡도는 O(n ^ 2)다.