정렬 알고리즘 - 버블 정렬의 이해와 효율적 구현 방법

버블 정렬 개요

• 인접한 두 개의 요소를 비교하여 필요에 따라 위치를 교환합니다.
• 정렬되지 않은 요소가 정렬된 순서로 이동하는 원리로 동작합니다.

버블 정렬 동작 원리

1. 배열의 첫 번째 요소부터 시작하여 그 다음 요소와 비교합니다.
2. 비교 후 조건에 해당되면 서로 위치를 교환합니다.
3. 교환된 요소와 그 다음 요소를 비교합니다.
4. 정렬이 완료될때까지 반복합니다.
5. 요소끼리 비교할때 위치의 이동 변화가 없으면 정렬이 끝난것입니다.

버블 정렬 코드 예시

function test(arr) {
 const n = arr.length
 let finished
 for(let i = 0; i < n - 1; i++) {
  finished = true
  for(let j = 0; j < n - i - 1; j++) {
   if(arr[j] > arr[j+1]) {
    finished = false
    [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
   }
  }
  if(finished) break
 }
}

const arr = [5,4,3,2,1]
test(arr)

• 결과는 1,2,3,4,5로 나옵니다. 반대의 결과가 나오기 위해서는 if(arr[j] < arr[j+1])로 바꿔야합니다.
• 위치 교환은 es6 구조 분해 할당 문법입니다.

버블 정렬 시간 복잡도

• 이미 정렬된 배열일 경우 안에 for문 한번만 돌면 되기때문에 O(n)이 걸립니다.
• 최악이나 평균의 경우 O(n^2) 시간 복잡도를 가집니다.

버블 정렬 장점

• 구현이 간단합니다.
• 작은 크기의 배열이나 거의 정렬된 배열에서 효율적입니다.

버블 정렬 단점

• 배열의 크기가 클수록 비효율적입니다.
• 많은 수의 교환 작업이 필요하므로 처리 속도가 느립니다.

버블 정렬 활용

• 이해하기 쉬워서 알고리즘 학습의 첫 걸음으로 활용됩니다.