버블정렬(Bubble Sort)

컴퓨터 과학 분야에서 대대로 이어져 내려온 고전 알고리즘 중 "버블정렬"을 알아보고자 한다.

정렬 알고리즘은 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 지난 수년간 수십 개의 정렬 알고리즘이 개발돼 왔다. 이러한 알고리즘은 모두 공통된 문제를 해결한다.
정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까?

버블정렬은 알고리즘에서 단순 정렬이라고 분류된다.
이해하기 쉬워서 이렇게 불리지만 정렬 알고리즘 중에선 비효율적인 알고리즘이다.

---

버블정렬의 단계

1. 배열 내에서 연속된 두 항목을 가리킨다.(처음에는 배열의 첫 번째 원소부터 시작해서 처음 두 항목을 가리킨다.) 첫 번째 항목과 두 번째 항목을 비교한다.

ex>
패스스루 1 : 인덱스0 > 인덱스1
패스스루 2 : 인덱스1 > 인덱스2
...

2. 두 항목의 순서가 뒤바뀌어 있으면(즉, 왼쪽 값이 오른쪽 값보다 크면) 두 항목을 교환(swap)한다.(순서가 올바르다면 아무 것도 하지 않는다.)

ex>
패스스루 1 : 인덱스 0, 인덱스1 = 인덱스 1, 인덱스 0
패스스루 2 : 인덱스 1, 인덱스2 = 인덱스 2, 인덱스 1
...

3. "포인터"를 오른 쪽으로 한 셀씩 옮긴다.

ex>
패스스루 1 : 인덱스 0, 인덱스1 (포인터 위치)
패스스루 2 : 인덱스 1, 인덱스2 (포인터 위치)
...

4. 배열의 끝까지 또는 이미 정렬된 값까지 1단계부터 3단계까지 반복한다.

5. 이제 두 포인터를 다시 배열의 처음 두 값으로 옮겨서 1단계부터 4단계를 다시 실행함으로써 새로운 패스스루를 실행한다. 교환이 일어나지 않는 패스스루가 생길 때까지 패스스루를 반복한다. 교환할 항목이 없다는 것은 배열이 정렬됐고 문제를 해결했다는 뜻이다.

코드

코드설명

boolean sorted = false; 

교환이 일어났는지 여부 false일 경우 교환이 일어났다고 보고, true일 경우는 교환이 일어나지 않았다고 판단한다.

repeat -= 1;

가장 큰 수 부터 맨 뒤로 하나씩 맞춰가며 동작하므로 정렬이 완료된 인덱스는 탐색할 필요가 없다.