[알고리즘] 버블 정렬(Bubble Sort) [값을 비교하여 뒤에서부터 정렬하는 정렬 알고리즘]

---

- 버블 정렬(Bubble Sort)이란?

버블 정렬은 1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n－1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n－2번째와 n－1번째까지, ... 해서 최대 n(n－1)／2 번 정렬한다.
→ 한 번 돌 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여 버블 정렬이다.

버블 정렬(Bubble Sort)의 예시

- 버블 정렬의 효율성?

거의 모든 상황에서 최악의 성능을 보여준다.
단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다.
→ 만들기가 쉽고 직관적일 뿐이지 알고리즘적 관점에서 보면 대단히 비효율적인 정렬 방식

---

- 버블 정렬의 파생형

1. 칵테일 정렬(cocktail sort)

셰이커 정렬(shaker sort)라고도 한다. 홀수 번째 돌 때는 앞부터, 짝수 번째는 뒤부터 훑는 정렬. 마지막과 처음이 번갈아가며 정렬된다.
→ 마지막과 처음을 번갈아가며 정렬하는 과정이 칵테일을 섞는 것과 비슷해보인다 하여 칵테일(혹은 이름을 합쳐서 칵테일 셰이커) 정렬이다.

칵테일 정렬(cocktail sort)의 예시

2. 콤브 정렬(comb sort)

기본 형태는 버블정렬과 같지만, 예를 들어 처음에 a[0]에서 10칸 띄워서 a[11]과 비교해서 치환하는 식으로 대상을 띄웠다가 한 바퀴 돌면 띄우는 간격을 좁혀서 정렬하는 방식

콤브 정렬(comb sort) 예시