JavaScript에서 정렬 알고리즘 삽입

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

삽입 정렬이란 무엇입니까?

알고리즘의 Wikipedia page 설명:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. ... Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

이것은 듣기에 약간 곤혹스러울 수도 있지만, 여기에 유용한 시각화 알고리즘이 데이터를 어떻게 처리할 것인가가 있다.

우리가 하나의 정수 그룹에서 이동할 때, 모든 값은 한 번씩 이전의 정수와 비교하고, 모든 값과 위치를 교환하여, 그것이 최종적으로 정확한 위치에 삽입될 때까지 한다.
데이터를 처리할 때, 우리는 왼쪽은 정렬되고, 오른쪽은 정렬되지 않은 두 개의 하위 그룹을 얻었다.

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

불행하게도, 삽입 정렬은 대형 데이터 집중의 효율이 더 높은 알고리즘보다 낮다. 예를 들어 빠른 정렬, 무더기 정렬 또는 합병 정렬은 확실히 어떤 장점을 가지고 있지만.

프로그래밍이 쉽다.

는 작은 데이터 집합에 유효하다.

이미 대부분의 정렬된 데이터 집합에 대해 자체 적응 효율을 가진다.

기능은 일정한 O(1) 공간만 차지합니다.

삽입 정렬의 최악의 상황과 평균 상황의 시간 복잡도는 모두 O(n2)(2차)

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

지금 저희가 멋진 부분에 들어갔어요!
JavaScript에서 정렬을 삽입하기 때문에, 우리는 현대 ES6+ 문법을 이용하여 수조의 교환 요소를 처리할 것입니다. 이것은 우리가 써야 할 코드 줄 수를 유지하는 데 도움이 될 것입니다.
다음은 최종 알고리즘의 모양입니다.

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      [array[j - 1], array[j]] = [array[j], array[j - 1]];
      j--;
    }
  }
return array;
}

이제 한 걸음 한 걸음 그것을 분해합시다.
우선, 함수, 반환값 (수정된 그룹) 과 주 for 순환을 설명하고, 그 중에서 모든 논리를 실행합니다.

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {

  }
return array;
}

우리는 그것을 매우 예측할 수 있는 for순환으로 썼다. 그것은 단지 전체 그룹에서 교체될 뿐이다.다른 점은 색인 1부터 시작하는 것이지 일반적인 0이 아니라는 점이다.이것은 우리가 항상 모든 원소를 이전의 원소와 비교하여 교환이 필요한지 확인하기 때문이다.0번째 원소는 이전 원소와 비교할 수 없기 때문에, 우리는 그것을 건너뛰고 1부터 시작합니다.
다음은 두 번째 포인터를 만들어서 그룹 j를 훑어보는 데 사용합니다.

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
  }
return array;
}

포인터 j는 i의 값으로 설정됩니다. 포인터 순환 중인 그룹을 앞으로 훑어볼 때, 우리는 순식간에 두 번째while 순환을 실현할 것입니다. 이 순환은 정렬된 하위 그룹의 모든 값과 비교하기 위해 뒤로 훑어볼 것입니다.
while 순환, 그리고 우리 알고리즘의 마지막 단계는 다음과 같다.

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      [array[j - 1], array[j]] = [array[j], array[j - 1]];
      j--;
    }
  }
return array;
}

이것은 많은 새로운 코드입니다. 이 세 줄의 코드가 모두 무엇을 했는지 봅시다.

우리는while 순환을 실현했다. j가 0보다 크고 (그것이 아직 수조의 시작에 도달하지 않았다는 것을 의미함) 수조 [j]의 값이 수조 [j-1]보다 작을 때 이 순환은 촉발될 것이다.이 두 가지 조건은 시작 요소가 적당한 위치에 삽입될 때까지 순환을 수조를 따라 아래로 옮겨다니며 값을 교환할 수 있게 할 것이다.

JavaScript ES6 구문을 사용하여 각 요소를 이전 요소와 교환하고 시작 요소를 한 단계씩 아래로 이동합니다.

우리는 j의 값을 줄였기 때문에 다음 순환에서 우리는 다음 순환에서 시작하는 같은 원소를 교환하고 있다.

이렇게!우리는 이제 JavaScript에서 정렬 알고리즘을 삽입하는 데 성공했다.대단히 좋다
이 모든 것은 당신이 상상하고 생각해야 하기 때문에 순환과 지침을 생각하도록 격려합니다. 클릭을 하면 영원히 고정됩니다.나도 여기서 이 유용한 애니메이션을 다시 붙일 것이다. 왜냐하면 이것은 가시화하고 있는 일에 큰 도움이 된다고 생각하기 때문이다.

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