[자료구조(C언어)] 정렬 1 - 버블 정렬 (bubble sort)

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

버블 정렬

배열에서 서로 인접한 두 원소를 검사하여 큰 값을 뒤로 보낸다.

이것을 배열의 끝에 도달할 때까지 반복하면

인덱스 0 ~ n-1까지의 원소들 중에서 가장 큰 값(/작은 값)을 맨 뒤(n-1)로 보내게 된다.

(n-1은 다음 정렬에서 제외된다. 정렬이 수행될 때마다 제외되는 원소가 뒤에서부터 하나씩 늘어난다. )

↓

같은 방법으로

0~ n-2까지의 원소들 중에서 가장 큰 값을 n-2로 보내기

(n-2가 정렬에서 제외됨)

0~ n-3까지의 원소들 중에서 가장 큰 값을 n-3으로 보내기

(n-3이 정렬에서 제외됨)

...

0~1까지의 원소들 중에서 큰 값을 1로 보내기

 

위와 같은 과정을 거쳐 오름차순 정렬을 할 수 있고

큰 값을 뒤로 보내는 대신 작은 값을 뒤로 보내면 내림차순 정렬을 할 수 있다.

 

오름차순 버블 정렬 코드

void bubbleSort(int data[], int n) {
	for (int i=n-1; i>0; i--) {
		for (int j=0; j<1; j++) {
			if (data[j] > data[j+1]) {
				int tmp = data[j];
				data[j] = data[j+1];
				data[j+1] = tmp;
			}
		}
	}
}

 

원소를 교환(SWAP)할 때는

tmp = data[j];

data[j] = data[j+1];

data[j+1] = tmp;

위와 같이 세 번의 치환 연산이 필요하다.

 

data[j] = data[j+1];

data[j+1] = data[j];

위와 같이 두 번 연산하면 원래 data[j]의 값이 사라지기 때문에 제대로 치환을 할 수 없다.

원래 data[j]의 값을 tmp에 저장한 후 tmp를 이용해 두 변수의 값을 교환해야 한다.

 

버블 정렬의 시간복잡도는 ?

O(n^2)

최악, 평균과 관계없이 모두 일정하다.

버블 정렬 알고리즘 자체는 구현이 매우 간단하지만, 데이터의 교환(SWAP)이 복잡하기 때문에 거의 쓰이지 않는다. (구현은 쉽지만 효율이 낮음)