버블정렬(Bubble Sort)

버블정렬(Bubble Sort)

버블정렬이란?

인접한 두 항목의 값을 비교해서 일정한 기준을 만족하면 서로의 값을 교환하여 정렬하는 방식입니다. 예를 들어, 오름차순 정렬은 두 항목의 값을 비교하여 앞쪽 값이 더 크면 두 항목의 값을 교환하고 내림차순 정렬은 두 항목의 값을 비교하여 앞쪽 값이 더 작으면 두 항목의 값을 교환하는 방식입니다. 다른 정렬 알고리즘에 비해 속도가 상당히 느린 편이지만, 코드가 단순하여 사용도가 높습니다. 버블정렬은 최악의 경우 O(n^2)의 시간복잡도가 걸립니다.
아래 그림을 참고하시면 조금 더 이해에 도움이 되실겁니다!

코드

두 개의 반복문이 필요합니다. 내부 반복문에서는 첫번째 값부터 이전 패스에서 뒤로 보내놓은 값이 있는 위치전까지 앞뒤 값을 계속해서 비교해나가면서 앞의 값이 뒤의 값보다 클 경우 자리 교대(swap)를 합니다. 외부 반복문에서는 뒤에서부터 앞으로 정렬 범위를 n-1부터 1까지 줄여나갑니다.

참고: [블로그](