버블 정렬 (Bubble Sort)

| 버블 정렬

버블 정렬은 오름차순을 예로 들었을 때 가장 작은 숫자와 바로 옆인 큰 숫자를 비교하며 위치를 바꿔주는 알고리즘이다.

더 큰 숫자가 한번에 하나씩 이동한다.

이 알고리즘은 제일 큰 숫자를 맨 뒤로 이동 시키며 정렬을 한다.

 

| 작동 원리

 

0번째 부터 loop를 실행하고 첫 순서는 14와 21을 비교한다.

14는 21보다 크지 않음으로 위치를 바꾸지 않고 21과 37을 비교한다.

21 또한 37보다 크지 않음으로 위치를 유지한다.

그리고 37과 5를 비교한다.

37을 5보다 큼 으로 위치를 바꿔준다.

계속해서 이런 방식으로 진행 하다 보면

첫번째 loop 이후

마지막 숫자가 정해진다.

그리고 계속해서 똑같은 작업을 반복한다.

반복 이후 이렇게 오름차순 으로 정렬 된다.

 

| 버블 정렬 구현 [JS]

구현은 이중 for문을 돌며 현재의 값이 다음 값보다 크면 배열의 위치를 바꿔준다.

ES2015 문법을 사용했다.

기존에 사용하던 temp변수를 만들어서 위치를 바꿔줘도 상관없다.

또한 swap이라는 함수를 만들어서 사용해도 무관하다.

 

이 코드에는 문제점이 있다.

무조건 전체요소를 비교하고 순회 한다는 것이다.

 

확실하게 알아보려면 이중 for문 내부에서 console 로 numbers를 출력 해보면 총 15번이 출력된다.

그래서 코드를 최적화 하면 불필요한 loop는 실행 할 필요가 없다.

 

| 버블 정렬 최적화 [JS]

기존의 코드와 동일하지만 isSwap이라는 변수를 선언하고 기본값으로 true를 할당했다.

이 코드는 해당 요소가 뒤의 요소보다 크면 위치를 바꾸고 isSwap을 false로 값을 바꾼다.

그렇게 되면 불필요한 loop는 돌 수 없다.

최적화 작업을 진행 하기 전에는 console이 15번 출력 되었지만

진행 이후에는 8번이 출력 되었다.

 

| 버블 정렬의 BigO

최적화를 진행하기 전 에는 n의 제곱 시간을 가지지만 최적화를 진행한다면 선형시간 (linear time) 을 가질 수도 있다.