버블정렬

비교 기반 정렬 알고리즘으로, 양 옆에 위치한 두 값을 비교하면서 크기 순으로 정렬.

배열의 뒤에서부터 정렬됨.

 

 

오름차순으로 버블 정렬을 수행할 때 작동 방식 

...

a

b

...

 

a<b

...

a

b

...

 

b<a

...

b

a

...

 

 

배열의 첫 번째 요소부터 마지막 요소까지 비교하며 정렬하면 최대값이 배열에 마지막에 위치한다.

배열의 n번째 요소를 정렬하 데 n-1번 비교하므로, 배열의 모든 요소를 정렬하려면 (n-1) + (n-2) + ...+ 2 + 1 = n(n-1) / 2

시간 복잡도 O(n²)

 

정렬을 수행하는 데 비교적 느린 편이지만, 별도의 메모리 공간이 필요하지 않음.