[알고리즘] 버블 정렬 (Swift)

버블 정렬이란?

현재 원소와 바로 다음 원소의 값을 비교하여 조건에 맞으면 교환하는 방식으로 정렬합니다.

원소의 이동이 거품이 수면으로 올라오는 것과 비슷한 모습을 보이기에 버블 정렬이라는 이름이 지어졌다고 합니다.

동작 방식

[5, 1, 3, 9, 4, 2, 7, 8, 6] 이라는 Int 배열이 있다고 가정해보겠습니다.

오름차순으로 정렬하려면 어떤식으로 동작할까요?

Step 1

현재 원소 5와, 다음 원소 1과 비교합니다.
5가 더 크기 때문에 5와 1의 위치를 변경합니다.

현재 원소 5와 다음 원소 3과 비교합니다.
5가 더 크기 때문에 5와 3의 위치를 변경합니다.

현재 원소 5와 다음 원소 9를 비교합니다.
9가 더 크기 떄문에 위치를 변경하지 않습니다.

이것을 계속 반복하면 배열이 다음과 같이 변경 될 것입니다.

이제 9는 정렬이 되었습니다.

Step 2

이제 9는 정렬이 되어있기 때문에
첫번째 원소부터 8번째 원소까지 값을 비교해주면 됩니다.

몇 번만 더 해볼까요?
현재 원소 1과 다음 원소 3을 비교합니다.
3이 더 크기 때문에 위치를 변경하지 않습니다.

현재 원소 3과 다음 원소 5를 비교합니다.
5가 더 크기 때문에 위치를 변경하지 않습니다.

현재 원소 5와 다음 원소 4를 비교합니다.
5가 더 크기 때문에 위치를 변경합니다.

이것을 계속 8번째 원소까지 반복하면 배열이 다음과 같이 변경 될 것입니다.

Step 3

Step 4

이미 정렬이 되었네요.
하지만 컴퓨터는 정렬이되었는지 모르기 때문에, 더 반복을 할 것입니다.

시간 복잡도

최악, 최선, 평균 모두 $O(n^2)$ 입니다.
정렬이 되어있어도 계속해서 비교하기 떄문입니다.

공간 복잡도

배열 안에서 교환을 통해 정렬을 하기 때문에 더 필요한 공간이 필요하지 않습니다.

따라서 $O(1)$ 입니다.

Stable?

안정 정렬 입니다.
[1, 4, 3, 4] 라는 배열이 있을 때, 앞에 있는 4가 뒤에 있는 4보다 앞에 위치하기 때문에 안정 정렬입니다.

In-Place?

In-Place 정렬입니다.
정렬하고자 하는 배열 안에서 교환하는 방식이고, 다른 메모리 공간이 필요하지 않기 때문입니다.

소스코드