정렬 알고리즘(버블 정렬)

버블 정렬(Bubble Sort)

개yo

---

저번 포스팅에서는 선택정렬 알고리즘에 대해 알아 보았고, 이번 포스팅에서는 버블정렬 을 구현하고 시간 복잡도를 알아 보도록 하겠다.

문제

---

문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라

1 10 5 8 7 6 4 3 2 9

SOL

문제를 해결하기 위해 “옆에 있는 값과 비교하여 작은값을 앞으로 보내기”를 이용할 수 있다.

위와 같은 방법을 우린 버블정렬 이라고 부른다.특징

정렬 알고리즘 중 가장 구현하기 쉽다.

가장 비효율적인 방법이다.

구현

---

#include <iostream>

using namespace std; 

int main(void) {
	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++) {
			// index j, j+1과  비교하여 조건에 맞으면 두 index를 바꾼다. 
			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]);
	}
	return 0;
}

출력 값

1 2 3 4 5 6 7 8 9 10

해설

---

위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.

1. 단순 반복적으로 두 숫자를 비교하여 앞으로 보낸다.
2. 각 사이클 마다 가장 큰 값이 맨 뒤로 보내지게 된다.

위 두 과정은 컴퓨터의 내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 느린 안좋은 알고리즘이라고 할 수 있다.

시간 복잡도는 선택정렬 과 동일하게 O(N^2) 로 표현할 수 있다.

본 포스팅은 동빈나님의 블로그를 참고하여 작성하였습니다.