거품 정렬

1 개요

bubble sort, sinking sort

거품 정렬, 버블 정렬, 버블 소트

• 두 인접한 원소를 검사하여 정렬하는 방법
• 제일 큰 값을 맨 뒤로 보내는 일을 반복
• 시간 복잡도: [math]\displaystyle{ O(n^2) }[/math]
• 상당히 느리지만 코드가 단순하고 직관적임
• 보통 이중 for 루프로 구현
• 교환 정렬의 하나

2 예시

<?php
function xmp_print($arr) { echo '<xmp>'; print_r($arr); echo '</xmp>'; }

function bubble_sort(&$arr) {
	$size = count($arr);
	for($i=0; $i<$size; $i++) {
		for($j=0; $j<$size-$i-1; $j++) {
			if($arr[$j+1] < $arr[$j])
				$arr[$j] ^= $arr[$j+1] ^= $arr[$j] ^= $arr[$j+1]; // swap
		}
	}
}

$arr = range(1,10);
shuffle($arr);
xmp_print($arr);
bubble_sort($arr);
xmp_print($arr);

→ if($arr[$j+1] < $arr[$j])에서 부등호 방향을 반대로 하면 내림차순이 된다.

→ 예제: http://zetawiki.com/ex/php/bubble_sort.php

3 같이 보기

• 삽입 정렬
• 병합 정렬
• 정렬
• swap
• 다언어 거품정렬

5 참고 자료

• https://en.wikipedia.org/wiki/Bubble_sort