[알고리즘] 버블 정렬 [Bubble Sort]

[알고리즘] 버블 정렬 [Bubble Sort]

버블 정렬은 가장 단순한 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 필요시 위치를 교환하는 방식으로 동작합니다.

이 과정을 배열이 정렬될 때까지 반복합니다.

 

 

 

동작 원리

• 배열의 첫 번째 원소부터 시작하여 인접한 원소와 비교합니다.
• 현재 원소가 다음 원소보다 크다면 두 원소의 위치를 교환합니다.
• 배열의 끝까지 이 과정을 반복하면 가장 큰 원소가 배열의 끝으로 "버블링"됩니다.
• 이 전체 과정을 배열이 완전히 정렬될 때까지 반복합니다.

 

 

 

예시

function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;         
      }
    }
    // 최적화를 위해 이전 루프에서
    // 교환이 이루어지지 않았다면
    // 루프 멈춰
    if(noSwaps) break;
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);




// 다른 버전
function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
      	// 이런식으로 ES6 방식 사용가능
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        noSwaps = false;         
      }
    }
    // 최적화를 위해 이전 루프에서
    // 교환이 이루어지지 않았다면
    // 루프 멈춰
    if(noSwaps) break;
  }
  return arr;
}

 

 

 

 

시간 복잡도

• 최악의 경우: O(n^2)
• 최선의 경우: O(n) (이미 정렬된 배열)
• 평균: O(n^2)

 

 

공간 복잡도

• O(1) - 추가적인 메모리 공간을 거의 사용하지 않습니다.

 

 

장단점 

장점

• 구현이 매우 간단하고 이해하기 쉽습니다.
• 추가 메모리 공간이 거의 필요하지 않습니다.

 

단점

• 대규모 데이터셋에 대해 비효율적입니다.
• 다른 정렬 알고리즘에 비해 일반적으로 성능이 떨어집니다.

 

 

 

최적화 방법

• 이미 정렬된 부분은 다시 검사하지 않도록 최적화할 수 있습니다.
• 한 패스에서 교환이 일어나지 않았다면 정렬이 완료된 것으로 간주하고 종료할 수 있습니다.

 

 

실제 사용 버블 정렬은 주로 교육 목적으로 사용되며, 실제 애플리케이션에서는 더 효율적인 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)을 사용하는 것이 일반적입니다.

 

 

결론

버블 정렬은 간단하지만 비효율적인 정렬 알고리즘입니다.

그럼에도 불구하고, 알고리즘의 기본 개념을 이해하는 데 좋은 시작점이 될 수 있습니다.

 

 

 

참조!

https://www.udemy.com/course/best-javascript-data-structures/