[자료구조] 버블 정렬 (bubble sort)

버블 정렬이란?

버블 정렬은 두 개의 인접한 원소를 비교해 순서에 맞지 않으면 서로 교환하는 정렬 방식입니다. 이렇게 인접한 원소를 교환하는 모습이 마치 물 속의 거품과 비슷해 버블 정렬이라고 부르는 것입니다.

 

순서에 맞지 않은 원소들을 교환하다 보면 오른쪽 리스트는 자동으로 정렬되기 시작합니다. 이 과정에서 왼쪽 리스트에 있는 원소들을 반복적으로 교환하면 정렬이 완료됩니다.

 

 

버블 정렬 구현

버블 정렬의 핵심은 비교 후 순서에 어긋나면 교환하는 것입니다.

 

각자 아래 목적에 맞게 분리되어야 하므로 반복문을 통해 숫자가 담겨있는 배열이나 리스트에 제대로 접근해야 합니다.

• 왼쪽 리스트: 인접한 원소의 순서가 맞지 않으면 바꿔줍니다.
• 오른쪽 리스트: 리스트 끝에서부터 정렬이 되어 있는 상태이므로 이 안에서 절대 자리를 바꾸면 안됩니다.

 

코드로 구현하면 아래와 같습니다.

void bubble_sort(int list[], int n) {
	int temp;
	for(int i = n - 1; i > 0; i—) {
		for(j = 0; j < i; j++) {
			// 앞 뒤를 비교한 후 순서에 맞지 않으면 교체
			if(list[j] > list[j + 1]) {
				SWAP(list[j], list[j + 1], temp);
			}
		}
	}
}

 

 

 

버블 정렬의 시간 복잡도

버블 정렬 상한

버블 정렬은 반복문이 이중으로 들어가 있기 때문에 $O(n^2)$입니다.

 

 

버블 정렬 하한

이미 정렬된 경우 버블 정렬은 실행시간의 하한으로 $O(n)$의 시간 복잡도를 가질 수 있다.

 

아래 사진은 $O(n^2)$으로 나와있어 유의가 필요하다.

 

 

 

[자료구조] 선택 정렬 (selection sort)

[자료구조] 삽입 정렬 (insertion sort)

[자료구조] 셸 정렬 (shell sort)

[자료구조] 합병 정렬 (merge sort)

[자료구조] 퀵 정렬 (quick sort)

[자료구조] 힙 정렬 (heap sort)

[자료구조] 기수 정렬 (radix sort)