JavaScript에서 정렬 알고리즘 선택

제 JS 시리즈 정렬 알고리즘의 또 다른 항목에 오신 것을 환영합니다!지난주 게시물에 소개했으니 관심 있으면 보세요.

소개

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

정렬 선택은 무엇입니까?

The Wikipedia Page의 선택 정렬은 다음과 같은 알고리즘에 대해 설명합니다.

Selection sort is an in-place comparison sorting algorithm.
...
The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list.

Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

만약 가시화되지 않았다면 이것은 약간 곤혹스러울 수도 있습니다. 따라서 여기에 원근도에 모두 넣을 수 있는 애니메이션이 있습니다.

우리가 초기 순환에서 그룹을 훑어볼 때, 우리는 플러그인 순환 중의 두 번째 바늘을 사용하여 그룹에서 전진하고, 모든 값과 시작 값을 비교한다. (첫 번째 순환의 초기 색인부터)만약 우리가 비교적 낮은 값을 찾게 된다면, 우리는 이 새 값을 비교할 새로운 최저값으로 설정하고, 계속 밀어 넣을 것이다.
이렇게 함으로써 우리는 매번 수조를 훑어볼 때마다 다음 최소값을 찾을 수 있도록 확보한다.두 번째 순환의 끝에 도달했을 때, 우리는 최저 값을 첫 번째 초기 색인 값과 교환하고, 다음 단계를 계속할 것이다.
만약 우리가 최고에서 최저까지 정렬하는 것에 흥미가 있다면, 반대로 최대치를 검색할 수도 있다.이것은 너의 선택이다!

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

정렬을 선택하는 것은 상대적으로 이해하기 쉽고 실현하기 쉽지만, 유감스럽게도 대형 데이터 집합의 빠른 정렬, 무더기 정렬, 합병 정렬 등 다른 정렬 알고리즘에 뒤떨어진다.
그러나 정렬 기능을 선택하고 보조 메모리가 필요하지 않기 때문에 다른 복잡한 알고리즘에 비해 공간적 우위를 가진다.
일반적으로 그것은 프로그래머와 컴퓨터 과학자로서 정렬을 선택하는 것이 여전히 중요하지만, 성능이 더 높은 대체 방안일 수도 있다.
정렬의 최적 상황, 최악 상황, 평균 상황을 선택할 때 복잡도는 O(n^2)로 본질적으로 항상 두 번이라는 것을 의미한다.

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

이것이 바로 즐거움의 시작이다!
JavaScript에서 정렬을 삽입하기 때문에, 우리는 현대 ES6+ 문법을 이용하여 수조의 교환 요소를 처리할 것입니다. 이것은 우리가 써야 할 코드 줄 수를 유지하는 데 도움이 될 것입니다.
다음은 최종 알고리즘의 모양입니다.

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }     
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

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

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

  }
  return array;
}

왜 우리가 정상적인 것이 아니라 순환이 멈췄는지 알고 싶을지도 모른다.이것은 다음 순환에서 우리가 먼저 array.length - 1 를 진열의 이웃 array.length 과 비교할 것이기 때문이다.이것은 색인을 전체 수조의 길이보다 짧게 하기 위해 초기 순환을 멈춰야 한다는 것을 의미한다.
다음은 현재 최소 요소 인덱스를 저장하는 변수 i 와 비교 작업을 수행하는 두 번째 순환을 설명합니다.

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {

    }

  }
  return array;
}

보시다시피 이 순환은 i + 1 부터 시작하여 이 값을 포인터 minIndex 에 분배합니다.i + 1 변수는 이 사이클 내에서 변경될 가능성이 높기 때문에 임시 측정값으로만 설정됩니다.그러나 j 실제로는 수조의 정렬되지 않은 부분 중의 다음 최소값일 수도 있고 원래의 위치에 머무를 수도 있다.
마지막으로 가장 중요하지 않은 점은 중첩 루프에 핵심 비교 논리를 추가하고 순환이 끝난 후에 두 개의 값을 교환하는 ES6 교환을 추가하는 것입니다.

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }     
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

본 강좌의 맨 위에서 되돌아본 바와 같이 정렬 선택의 핵심은 다음 최저치를 선택하고 그룹의 끝에 도달할 때까지 추적한 다음에 정렬 부분의 오른쪽 경계와 교환하는 것이다 (우리의 초기 minIndex 인덱스)
우리는 여기서 평가ifi를 통해 이 점을 실현한다.만약 그렇다면, 이것은 i 정렬된 부분의 끝에 교환해야 한다는 것을 의미한다. (더 낮은 값을 찾지 않으면)우리는 설정i을 통해 이 점을 실현한다.
이 순환이 끝난 후, 우리는 수조의 정렬되지 않은 부분에서 다음 최저치를 찾을 것이며, ES6array[j] < array[minIndex] 문법을 사용하여 그것을 적당한 위치로 교환할 것이다.
이렇게!우리는 JavaScript에서 정렬 알고리즘 선택에 성공했습니다.우후!
이 점에서 이전의 애니메이션을 다시 한 번 살펴볼 만하다. 이것은 우리가 방금 코드에서 한 모든 시각적 표시를 제공한다.

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