버블 정렬

표지 이미지 출처: Unsplash - Kai Dahms

소개

이것은 다양한 정렬 알고리즘, 몇 가지 설명 및 JavaScript 솔루션에 대한 빠른 데모에 대한 시리즈가 될 것입니다.

버블 정렬

우선 가장 기본적인 것인 버블 정렬부터 시작하겠습니다.
버블 정렬의 논리는 다음과 같습니다.

처음부터 시작하여 인접한 두 요소를 비교합니다

.

이전 것이 다음 것보다 크면 두 개를 교환하십시오

배열에 요소가 남아 있지 않을 때까지 반복합니다.

이것은 가장 큰 요소가 배열의 끝에 있도록 보장하는 단 한 번의 반복입니다.

배열의 모든 요소에 대해 이 프로세스를 반복합니다

.

복잡성

보시다시피 몇 가지 다른 결과가 있으며 비교할 요소의 수에 따라 상황이 빠르게 통제 불능 상태가 될 수 있습니다.

최상의 시나리오: 요소가 정렬된 경우 > O(n) 비교를 수행합니다.

최악의 시나리오: 요소가 역순으로 정렬된 경우 > O(n2) 비교를 수행합니다. 10개의 요소에 대해서는 문제처럼 보이지 않지만 1000개의 요소에 대해서는 첫 번째 선행 요소 뒤에 0이 많이 있을 것입니다. :)

평균 시나리오: 슬프게도 평균 시나리오는 최악의 시나리오와 시간 복잡도가 동일하며 여전히 O(n2)입니다.

용법

버블 정렬은 이해하기 쉽기 때문에 그렇게 문제가 되지 않는다고 생각합니다. 현명하게 사용하고 소량의 요소에 사용하십시오. 최소한의 요소까지 문제가 없습니다.

구현

물론 이것을 구현하는 방법은 많이 있지만 관심이 있는 사람을 위해 여기에 남겨 둘 것입니다. 이를 위해 GitHub repo도 링크할 것입니다.

function bubbleSort(_array) {
  const array = _array;
  for (let i = 0; i < array.length - 1; i++)
    for (let j = 0; j < array.length - i; j++)
      if (array[j] > array[j + 1]) [array[j], array[j + 1]] = [array[j + 1], array[j]];

  return array;
}

일부 몰래 보기:

두 변수를 바꾸는 가장 쉬운 방법은 [a, b] = [b, a] > a tmp 다음

모든 반복이 끝날 때까지 배열을 반복할 필요가 없습니다 > 가장 큰 것이 이미 끝에 있는 경우(그리고 n번째로 큰 .. 등등) 그대로 두십시오

참조

Repo