[개념]선택정렬 / c / 제한시간 없음

▣ 문제

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 선택정렬입니다.

 

▣ 입력설명

- 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

▣ 출력설명

- 오름차순으로 정렬된 수열을 출력합니다.

 

▣ 입력 예시

6 13 5 11 7 23 15

 

▣ 출력 예시

5 7 11 13 15 23

 

<코드>

#pragma warning(disable:4996)
#include <stdio.h>

int main() {
	int n, i, j;
	int num[100];
	int temp;
	int index;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}

	for (i = 0; i < n - 1; i++) {
		index = i;
		for (j = i + 1; j < n; j++) {
			if (num[j] < num[index])index = j;
		}
		temp = num[i];
		num[i] = num[index];
		num[index] = temp;
	}

	for (i = 0; i < n; i++)
		printf("%d ", num[i]);
		
		
	return 0;
}

기존에 자주 사용할때는 swap하는 과정을 j for문에 넣어서 사용했는데

이는 swap하는 과정이 계속 반복되므로 비효율적이다.

그렇기 때문에 index라는 변수를 사용해서 j for문이 끝날때에만 가장 작은 수가 있는 index와 i를 swap하면 더 효율적인 코드를 만들수 있다.

알고리즘의 시간 복잡도는 O(N^2)이다.