버블 정렬

배열을 앞에서부터 훑으며 바로 옆 두 원소를 비교해 순서가 거꾸로면 맞바꾸는 일을 반복하는 정렬이다. 한 바퀴를 돌 때마다 가장 큰 값이 거품처럼 맨 뒤로 올라간다. 평균·최악 시간 복잡도는 O(n²)이고 같은 값끼리는 맞바꾸지 않으므로 안정 정렬이다.