알고리즘: 버블 정렬

소개

싱킹 정렬이라고도 하는 버블 정렬은 배열 또는 요소 목록을 반복하고 한 번에 두 요소를 비교하고 필요한 경우 교환하는 방식으로 작동하는 정렬 알고리즘입니다. 모든 요소가 제대로 정렬될 때까지 이 작업을 수행합니다. 작동하는 예를 살펴보겠습니다.

심상

알고리즘은 첫 번째 카드[8]에서 시작하여 인접한 카드[3]와 비교합니다. [8]이 [3]보다 크기 때문에 위치를 서로 바꿉니다. 이것이 버블 정렬의 핵심 개념입니다.



알고리즘은 각 요소가 적절한 위치에 올 때까지 한 번에 두 개의 요소를 검사하는 목록을 통해 이동합니다.

구현

이 알고리즘을 코드로 작성하기 전에 단계별로 분해하여 어떻게 작동하는지 이해해 보겠습니다.

배열 또는 목록을 반복합니다.

루프를 돌면서 현재 요소가 다음 요소보다 작거나 큰지 확인합니다.

현재 요소가 더 크면 요소의 위치를 ​​바꾸고 그렇지 않으면 다음 요소로 이동합니다.

스와핑이 발생하지 않을 때까지 반복합니다.

위의 단계는 javascript 코드에서 다음과 같습니다.

function bubbleSort (array){
    for (var i = 0; i < array.length; i++) { // loop
      if (array[i] && array[i + 1] && array[i] > array[i + 1]) { //comprare
       let currentIndex = array[i];
       array[i] = array[i + 1];   // swap
       array[i + 1] = currentIndex; // swap
     }
  }
  return array
}

위의 코드에는 문제가 있습니다. 배열을 한 번만 반복합니다. 배열의 모든 요소가 정렬될 때까지 루프를 계속 진행한 다음 루프를 종료할 방법이 필요합니다. 이를 위해 부울을 사용하여 현재를 나타냅니다. 배열의 상태와 배열의 상태가 정렬될 때까지 루프를 계속 유지하는 while 루프. 자바스크립트 코드에서 알고리즘은 다음과 같습니다.

function bubbleSort (array){
  let unsorted = true;
  while(unsorted){ 
    unsorted = false;
    for (var i = 0; i < array.length; i++) {
      if (array[i] && array[i + 1] && array[i] > array[i + 1]) {
       let currentIndex = array[i];
       array[i] = array[i + 1];
       array[i + 1] = currentIndex;
       unsorted = true;
     }
    }
  }
  return array
}

위의 함수에서 unsorted라는 변수를 초기화하고 값을 true로 설정합니다. unsorted가 true인 동안 배열을 계속 반복합니다. while 루프에 들어갈 때 정렬된 배열을 찾을 것이라고 가정하므로 unsorted를 로 설정합니다. 배열이 정렬되지 않은 경우 false입니다. 스왑이 발생하면 unsorted를 true로 설정하고 배열을 다시 반복합니다. 스왑이 발생하지 않고 정렬되지 않은 상태가 for 루프가 끝날 때까지 거짓으로 유지되는 경우에만 배열이 정렬되었음을 의미하기 때문에 함수를 종료합니다.

버블 정렬의 시간 복잡도

버블 정렬은 O(n2)의 최악 및 평균 복잡성을 가지며 다른 정렬 알고리즘과 비교하여 버블 정렬은 효율성이 매우 낮으며 프로그래머는 실제 문제를 해결할 때 사용하지 않는 것이 좋습니다.

결론.

버블 정렬은 이해하고 구현하기 쉽기 때문에 초보자 프로그래머에게 알고리즘 개념을 소개하는 교육 도구입니다.