Bubble Sort(버블 정렬)

✨ 버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다.

[ 97, 5, 10, 0, -30 ]

위의 배열에 들어있는 숫자를 오름차순으로 정렬해보자.

Bubble Sort 진행 과정

🎈버블 정렬 코드를 실행하면 위와 같은 과정으로 진행 된다.

이해하기 쉽게 하기 위해서, 예시 배열 숫자에는 가장 큰 수를 맨 앞에 그리고 가장 작은 수를 맨 뒤에 넣어보았다.

첫번째 사이클에서,
이웃한 데이터를 비교해가며 index를 하나씩 증가해 나가기 때문에 가장 큰 수(97)는 맨 뒤에 자리할 수밖에 없다.
첫 번째 index부터 '앞자리 > 뒷자리'기준으로 비교하기 때문이다. 97보다 큰 수가 없다면 앞의 비교문은 언제나 참이다.

하지만, 가장 작은 수는 맨 뒤에 있기 때문에 한 칸밖에 이동하지 못 한 것을 볼 수 있다.
이 내용을 볼 때, 가장 작은 수가 맨 앞에 위치하기 위해서는 배열의 크기만큼 반복문이 반복되어야 한다는 것을 알 수 있다.
또한, 이제 마지막 index는 비교 대상이 아니라는 것을 알 수 있다. 끝 index는 이미 정렬이 끝났다. 
따라서, 다음 비교 사이클에서는 index를 하나 줄여 비교를 진행해야 한다.

위의 과정이 반복되는 것이 버블 정렬이다. 이 내용을 토대로 코드를 작성해보겠다.

버블 정렬 최종 코드

🧨위에 보이는 것처럼 for loop 중첩으로 버블 정렬을 해결할 수 있다.

앞서 말한 것처럼 외부 for loop에서는 배열의 길이만큼 반복해준다.
내부 for loop에서는 외부 for loop이 한 사이클 돌 때마다, 마지막 index는 정렬이 끝나므로
배열의 길이 - i 만큼을 범위로 지정해준다.
그리고 내부 for loop에서 if 조건문을 이용해 뒤에 숫자보다 앞의 숫자가 크면 교체(swap)해주면 된다.

지금까지 버블 정렬을 이용해서 숫자를 정렬하는 방법을 작성해봤다.
하지만, 버블 정렬은 O(n^2)만큼의 시간 복잡도(Runtime complexity)를 갖기 때문에 시간적으로 굉장히 안 좋은 방법이다. 
하지만, 코드를 구현하기에는 가장 쉬운 정렬 방법이다.

다음 글에서는 같은 시간 복잡도지만, 다른 정렬 방법인 선택 정렬(Selection Sort)를 작성해보겠다.