2. 버블 정렬

문제: 1, 10, 5, 8, 7, 6, 4, 3, 2, 9를 오름차순으로 정렬해라.

1. 가장 앞에 있는 값과 바로 그 다음의 값을 비교하여 큰 것을 뒤로 보낸다.

2. 결국 맨 뒤는 가장 큰 값이 놓이게 된다.

3. 이 로직을 가장 큰 값이 놓이게 된 맨 뒤의 숫자를 빼는 방식으로 반복한다.

 

#include<stdio.h>

void main() {
	int i, j, temp;
	int array[10] = { 1,10,5,8,7,6,4,3,2,9 };

	//버블 정렬
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9 - i; j++) {
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
	//출력
	for (i = 0; i < 10; i++) {
		printf("%d", array[i]);
	}
}

 

시간 복잡도

0~9까지 비교하며 정렬

0~8까지 비교하며 정렬(맨 뒤는 어차피 가장 큰 값이니)

0~7

...

0~1

 

10 + 9 + ... + 2 + 1

n/2 * (n + 1) -> 나누기나 더하기 무시

n^2의 시간 복잡도를 갖는다.

 

<본 글은 유튜버 동빈나 님의 강의를 듣고 작성되었습니다.>