구현 방식

버블 정렬의 틀은 값을 지속적으로 두 값을 비교하여 큰 값을 뒤로 보내는 것이다. 이러한 형태가 수면 위로 거품이 떠오르는 것과 비슷하다하여 버블 정렬이라고 한다.

0번째 인덱스부터 배열의 끝까지 순차적으로 순회하며 값을 바꾸고(swap), 이후 1번째 인덱스부터 배열의 끝까지, 2번째 인덱스부터, ... n-1번째 인덱스부터 순회하며 값을 바꾼다.

시간 복잡도

버블 정렬은 정렬여부와 관계없이 $O(N^2)$으로 통인된다. 정렬여부와 관계없이 2개의 원소를 매번 비교하기 때문이다.

공간 복잡도

버블 정렬은 하나의 배열 내부에서 이루어진다. 따라서 배열의 크기인 $O(N)$이다.