[C] 백준 2750번 - 수 정렬하기

 시간 복잡도가 O(n^2)인 정렬 알고리즘은 교환 정렬, 선택 정렬, 삽입 정렬, 버블 정렬 등이 있지만, 버블 정렬을 공부해보려고 이 알고리즘을 사용했다.

 

 버블 정렬은 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환하는 알고리즘이다. 임의의 수가 여러 개 있고 오름차순으로 정렬할 때, 첫 번째 교환이 끝나면 마지막에는 가장 큰 수가 위치할 것이다. 두 번째 교환이 끝나면 두 번째로 큰 수가 마지막에서 두 번째에 위치할 것이다. 예시를 보며 알고리즘을 이해해보자. 

 

 ex) size=5, num[5]={5, 2, 4, 1, 3}이 있다.

이중 for문에서 첫 번째 for문 i는 각 단계에서 최대 교환 횟수와 인덱스 i미만까지 접근이 가능한 것을 의미한다.

이게 무슨 말이냐면 1단계 → i=4(최대 교환 횟수)가 되고 j=0, 0<4가 돼서 num배열의 0~3번까지 j가 접근(if문에서 j번째와 j+1번째를 비교하니까)할 수 있다.

두 번째 for문은 num[j]>num[j+1]이면 서로 교환하는 코드고 5가 가장 크니까 인접한 레코드와 비교하다보면 1단계가 끝났을 때 마지막에 위치할 것이다.

tag는 교환이 됐는지 확인하는 역할로 각 단계에서 교환이 일어나면 tag++;을 하는데, 만약 교환이 안됐으면(tag==0) for문을 break한다.

1단계 연산 결과 → num[5]={2, 4, 1, 3, 5}

2단계 연산 결과 → num[5]={2, 1, 3, 4, 5}

3단계 연산 결과 → num[5]={1, 2, 3, 4, 5}

4단계 연산 결과 → num[5]={1, 2, 3, 4, 5} 교환이 안됐고 tag는 0이니까 for문을 break해서 결과를 출력한다.

#include <stdio.h>

int main()
{
	int num[1000] = { 0, };
	int temp = 0;
	int tag = 0;
	int size;

	scanf_s("%d", &size);
	for (int i = 0; i < size; i++)
	{
		scanf_s("%d", &num[i], 1000);
	}
	for (int i = size - 1; i > 0; i--)
	{
		tag = 0;
		for (int j = 0; j < i; j++)
		{
			if (num[j] > num[j + 1]) // 교환
			{
				temp = num[j];
				num[j] = num[j + 1];
				num[j + 1] = temp;
				tag++;
			}
		}
		if (tag == 0)
			break;
	}
	for (int i = 0; i < size; i++)
	{
		printf("%d\n", num[i]);
	}
}

잘못된 점이 있으면 아래 댓글로 많이 남겨주세요!

감사합니다.