백준 2750번

백준 2750번은 정렬 알고리즘에 관한 문제이다. 오름차순으로 정렬한 후 출력하면 되므로, 우리가 본능적으로 가장 잘 알고 있을 법한 정렬인 선택 정렬(Selection Sorting)을 먼저 사용해보겠다.

선택 정렬이란, 배열에서 최솟값을 한번 찾고, 이를 맨 앞에 넣은 후에 맨 앞 수를 제외한 최솟값을 찾아 그 뒤에 붙이는 방식으로 정렬하는 알고리즘이다.

https://www.toptal.com/developers/sorting-algorithms/selection-sort

이 사이트에는 선택 정렬뿐만 아니고 다른 정렬도 있으니 둘러보면 좋을 것 같다.

직접 정리한 선택 정렬에 관한 그림은 위와 같다.

1. index를 맨 앞에 두고, 그 index에 들어있는 값과 비교해서 최소값을 찾는다.
2. 그 최소값과 index에 들어있는 값을 swap한다.
3. index를 한 칸 앞으로 옮기고, 위 작업을 반복한다.

이를 코드로 표현하면 다음과 같다:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int num;
	scanf("%d", &num);
	int* array = (int*)malloc(sizeof(int) * num); //배열의 크기는 모르므로, 동적 배열로 할당해준다. 
	for (int i = 0; i < num; i++) {
		scanf("%d", &array[i]); // 동적 할당해준 배열에 값을 입력받는다
	}
	for (int i = 0; i < num; i++) {
		for (int j = i; j < num; j++){
			if (array[i] > array[j]) { // 오름차순으로 정렬하기 위해 크기 비교
				int temp = array[i]; // 맞으면 swap
				array[i] = array[j];
				array[j] = temp;
			}
		}
	}
	for (int i = 0; i < num; i++) {
		printf("%d\n", array[i]);
	}
	free(array); // 동적 할당 해제
	return 0;
}