개념

• 가장 기초적인 알고리즘.
• 인접한 두 개의 요소를 비교해가면서 정렬을 진행하는 방식.
• 한 번 돌 때마다 마지막 요소가 정렬되는 것이 거품이 올라오는 것 처엄 보여 버블 정렬이라고 부른다고 한다.

이해

과정1

과정2(1과 4 스왑)

과정3

과정4

과정5(5와 2 스왑)

해당 과정을 반복하여 정렬

코드

과정6

function bubbleSort(arr) {
	let size = arr.length;
	for(let i = 0; i < size - 1; i++) {
		for(let j = 0; j < size - i - 1; j++) {
			if(arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1);
			}
		}
	}
}

특징과 시간 복잡도

• 장점: 구현이 매우 간단하다.
• 단점: 순서에 맞지 않는 요소들의 교환이 자주 일어난다.
• 시간 복잡도
  • 최악: O($n^2$)
  • 평균: O($n^2$)
  • 최선: O($n$) (정렬이 되어있는 경우)