JavaScript에서 기포 정렬 알고리즘 구현

제 JS 시리즈 정렬 알고리즘의 세 번째 항목에 오신 것을 환영합니다!이 두 문장과 이전 문장에서 소개했습니다. JS의 정렬 알고리즘에 대한 더 많은 정보를 알고 싶으면 이 문장들을 보십시오.

소개

컴퓨터 과학에서 정렬 알고리즘처럼 자주 사용하는 도구는 드물다.프로그래머와 엔지니어로서 우리는 매일 그것들에 의존하여 데이터를 선별하는데, 그것들은 거의 모든 현대 프로그래밍 언어에 이런저런 방식으로 삽입된다.
한 언어의 내장된 정렬 함수를 사용하면 대부분의 일상적인 작업을 완성할 수 있지만, 중요한 것은 엔진 뚜껑 아래에서 무슨 일이 일어났는지, 서로 다른 정렬 알고리즘이 실제로 무엇을 하고 있는지, 그리고 왜 이런 방식으로 일을 하는지 이해하는 것이다.자주 나타나지 않을 수도 있지만 기술 면접 환경에서 정렬 알고리즘을 실현하거나 해석할 수 있는 기회가 있습니다. 이것이 바로 본고가 당신을 위해 준비한 것입니다!
오늘 우리는 컴퓨터 과학에서 또 다른 주요한 정렬 알고리즘Bubble Sort을 배울 것이다.

기포 정렬은 무엇입니까?

Wikipedia page on Bubble Sort 알고리즘은 다음과 같습니다.

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.

교육 도구의 측면에서 볼 때 거품 정렬은 실제로 이해하고 실현해야 하는 가장 간단한 정렬 알고리즘 중의 하나이다.불행하게도, 그것도 효율이 가장 낮은 일종으로, 실제 프로그래밍 응용에서 거의 사용한 적이 없다.
본질적으로 이 알고리즘은 한 수조에서 여러 번 (또는 정렬된 수조의 가장자리 상황에서 한 번 교체됨) 각 원소를 이 수조의 오른쪽 원소와 비교하고 그것들을 교환하여 비교적 큰 원소가 오른쪽에 위치하도록 한다.반복 순환이 실행될 때마다 이 본질적으로 수조의 끝에 있는 최대 값까지 거품이 생기지만, 느리지만 반드시 값을 적당한 정렬 위치에 놓을 것이다.
다음은 알고리즘이 실행될 때 발생하는 일에 대한 유용한 시각적 표시입니다.

보시다시피, 매번 교체할 때마다 수조의 최대 값을 찾을 때까지 오른쪽으로 큰 값을 여러 번 교환합니다.간단하지만 임무를 완수했어!

그것의 효율은 얼마나 높습니까?

불행하게도'작업 완성'은 정렬 알고리즘의 유일한 요구가 아니다.앞서 언급한 바와 같이 거품 서열은 느리고 저효과로 유명한데, 주로 실용적인 도구가 아니라 교육 도구로 사용된다.가장 실제적인 목적에서 빠른 정렬, 무더기 정렬 또는 병합 정렬 등 다른 정렬 알고리즘을 시종 사용해야 한다.
다른 정렬 알고리즘에 비해 거품 정렬의 장점 중 하나는 핵심 논리에 수조가 정렬되었는지 확인하는 내장된 검사가 있다는 것이다. 정렬된 수조에 들어오면 O(n)가 실행될 때 수조를 한 번만 교체할 수 있기 때문이다.그러나 이것은 범수가 아니라 가장자리'최고의 상황'으로 간주될 수 있다. 다른 알고리즘은 이미 정렬된 수조를 검사하는 데 시간이 더 걸릴 수 있지만 거품이 생기는 정렬의 전체 효율은 여전히 낮다.
거품 정렬의 최악의 상황과 평균 상황이 실행될 때 복잡도는 O(n^2)이고 공간 복잡도는 O(n)이다.

우리는 어떻게 그것을 실시합니까?

지금, 나는 이미 성공적으로 당신에게 거품 정렬 (또는 영원히 그것을 피하고 싶게) 을 소개했는데, 우리 코드로 그것을 실현하기 시작합시다!
최종 JavaScript 코드는 다음과 같습니다.

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
  return array;
}

우리 그것을 몇 부분으로 나누자.
먼저 함수와 반환 값 (정렬 배열, 현지에서 수정) 을 설명합니다.

function bubbleSort(array) {

return array;
}

다음으로, 우리는 매우 중요한 변수 isSorted를 설명하고 이를 가브리엘 값으로 설정할 것이다.

function bubbleSort(array) {
  let isSorted = false;

  return array;
}

이것은 이상하게 보일 수도 있다. 왜냐하면 우리는 전송된 그룹이 정렬되었는지 모르겠지만, 그것은 곧 의미가 있을 것이다.본질적으로 말하자면, 우리가 하고 있는 것은 값을 false로 설정하여 시작하고, 이 값을 while 순환에서 벗어나는 방법으로 사용하는 것이다. 우리는 모든 논리를 그 안에 넣을 것이다. 다음과 같다.

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;

  }
return array;
}

보시다시피,while 순환은 !isSortedtrue로 돌아가면 isSorted === false 계속 실행됩니다.
순환이 시작될 때마다 값을 true 로 설정하면 순환이 중단됩니다.이것은 우리에게 무슨 도움이 됩니까?좋습니다. 다음 논리적 단계에서 만약 우리가 어떤 교환을 실행한다면, 우리는 수조를 두루 훑어보고 isSorted 를 false 로 설정할 것입니다.이것은 최소한 한 번의 교환을 실행하면 순환이 계속 운행된다는 것을 의미한다.마지막으로 정렬된 수조의 마지막 교체에서 isSorted 값은 true, while 순환이 끝납니다.
좀 곤혹스러워요?코드를 살펴보겠습니다.

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
return array;
}

방금 추가한 부분을 살펴보겠습니다.

for (let i = 0; i < array.length - 1; i++) {
  if (array[i] > array[i + 1]) {
    [array[i], array[i + 1]] = [array[i + 1], array[i]];
    isSorted = false;
  }
}

이 for 순환은 수조에서 끝날 때까지 1개의 값(array.length - 1을 교체하고 모든 원소의 값을 오른쪽의 원소(i + 1와 직접 비교한다
이전에 알고리즘에 대한 원시적인 설명과 시각화를 기억하고 있다면, 이것이 바로 우리가 현재 교환하는 값과 거품 수조 요소의 부분이다.이 강좌에서는 JavaScript ES6+ 구문[a, b] = [b, a] 형식으로 요소를 교환합니다.
만약 왼쪽의 값이 오른쪽의 값보다 크다면, 우리는 두 개의 원소를 교환하고 isSorted 를 false 로 설정합니다. 왜냐하면 우리는 수조가 이 순환에서 수조를 통해 완전히 정렬되지 않았다는 것을 알고 있기 때문입니다.
이제 우리는 알고리즘을 완성하기 위해 다시 한 번 그것을 함께 놓았다.

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
return array;
}

우리 끝났어!
논리를 다시 한 번 훑어봅시다.

우리는 isSorted 을 false 로 초기화할 것이다.

우리의while 순환은 isSorted true 과 같을 때까지 계속 운행한다. 이런 상황에서 그것은 멈춘다.

while 순환이 시작될 때마다isSortedtrue로 설정되어 있기 때문에 for 순환에서 교환이 실행되지 않으면while 순환이 종료됩니다.

for 순환에서 우리는 전체 수조를 훑어보고 값을 비교한다.한 값이 오른쪽보다 큰 이웃의 경우 이 두 값을 교환하고 계속하여 isSorted 를 false 로 설정합니다

우리는while 순환을 반복하여 수조에서 완전히 정렬될 때까지 여러 번 교체한 다음에 정렬된 수조를 되돌려줍니다.

논리 잠금을 돕기 위해 이 편리한 시각화를 다시 한 번 볼 것을 권장합니다.

만약 네가 이미 이렇게 멀리 갔다면, 너의 독서에 매우 감사할 것이다.나는 이것이 정렬 알고리즘, 자바스크립트, 프로그래밍 기초 지식을 배우는 모든 사람들에게 유용한 강좌가 되기를 바란다.😄
앞으로 댓글에서 더 많은 정렬 알고리즘을 연구할 테니 계속 지켜봐 주세요!