버블 정렬 알고리즘

버블 정렬 알고리즘은 순서가 잘못된 경우 인접 요소를 반복적으로 교체하는 방식으로 작동하는 가장 간단한 정렬 알고리즘입니다.

자바스크립트 구현

function bubbleSort(arr, l) {
  let flag;
  for (let i = 0; i < l; i++) {
    flag = false;

    for (let j = 0; j < l - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        flag = true;
      }
    }

    if (flag === false) {
      break;
    }
  }

  return arr;
}

설명

이 함수는 정렬해야 하는 배열과 길이라는 두 개의 매개변수를 받습니다. 배열의 길이를 쉽게 계산할 수 있는 언어를 사용하는 경우 두 번째 매개변수는 필수가 아닙니다.

첫 번째 루프는 배열 순회를 위한 것입니다. 배열의 각 요소를 남아 있는 모든 요소와 비교해야 하기 때문에 중첩 루프가 있습니다. l -1 -i 조건은 피하고 linstead만 사용할 수 있지만 이미 정렬된 요소와 비교하는 것은 유용하지 않기 때문에 알고리즘을 최적화하는 데 도움이 됩니다.

두 번째 루프에는 인접한 요소의 순서가 잘못된지 비교하는 조건이 있습니다(오름차순으로 정렬하는 경우 왼쪽 요소가 오른쪽보다 작아야 하며 내림차순 정렬의 경우 그 반대). . 이 프로세스는 배열 끝에 도달할 때까지 반복됩니다.

2행에는 flag라는 변수가 있습니다. 플래그는 알고리즘을 최적화하는 데도 도움이 됩니다. 첫 번째 루프의 각 랩에 대해 플래그는 거짓으로 재설정되고 잘못된 순서로 있는 요소를 찾으면 플래그가 참으로 설정됩니다. 이 접근 방식은 순회를 계속하는 것이 유용한지 알 수 있도록 도와줍니다. 한 랩 동안 잘못된 순서로 요소를 찾지 못하면 배열이 정렬되었다고 가정할 수 있기 때문입니다.

삽화:

그림으로 설명하자면 다음과 같습니다.
이 배열을 오름차순으로 정렬해야 합니다.



첫 번째 패스:



8은 첫 번째 요소이므로 남은 모든 요소와 비교해야 합니다. 8이 뒤의 요소보다 클 때마다 요소가 바뀌는 식으로 계속됩니다. 우리는 버블 정렬 알고리즘을 사용합니다. 첫 번째 패스에서 가장 높은 값(또는 정렬 순서에 따라 가장 낮은 값)이 목록의 맨 위로 이동합니다. 여기서 8은 목록의 맨 위에 있습니다.

두 번째 패스:



동일한 프로세스가 두 번째 랩에 대해 계속되고 7은 8이 이미 정렬되어 있고 중첩 루프의 이 조건 l -1 -i가 쓸모없는 비교를 방지하기 때문에 8과 비교되지 않습니다.

세 번째 패스:



네 번째 패스:

복잡성 분석:

버블 정렬은 알고리즘이 두 개의 중첩 루프를 사용하고 추가 공간을 사용하지 않기 때문에 공간 복잡도가 O(1)이므로 시간 복잡도는 O(n²)입니다.

결론:

버블 정렬은 시간 복잡도가 O(n²)이기 때문에 배열을 오름차순 또는 내림차순으로 정렬하는 데 도움이 되는 알고리즘이며 복잡도가 그렇지 않을 때 일반적으로 사용됩니다. 중요하거나 짧고 간단한 코드가 선호되는 경우. 이 기사를 읽고 새로운 것을 배우기를 바랍니다.

아무것도 🔺