JavaScript로 정렬해 보겠습니다.🔢

빠른 정렬, 병합 정렬, 삽입 정렬, 거품 정렬 등 다양한 정렬 알고리즘이 있는데 이런 알고리즘은 우리의 일상생활에서 매우 유용할 수 있으며 코드를 작성하여 생산 환경으로 운반할 수 있다.이 모든 것을 이해하는 것은 필요하지 않지만, 모든 것에 대해 기본적인 이해를 가지고 있다면, 당신은 당신의 장면에 가장 효과적인 것을 선택할 수 있습니다.

소개

차등 정렬 알고리즘을 선택하면 더 긴 완성 시간, 코드 복잡도, 더 나쁜 것은 프로그램이 작업 도중에 붕괴될 수 있다.
우리는 매일 정렬 알고리즘을 사용하는데, Array.sort 은 승순으로 수조를 정렬하는 데 사용되는 정렬 알고리즘 중의 하나이다.그러나 이것은 모든 장면의 해결 방안이 아니다.
정렬 알고리즘을 선택할 때, 우리는 복잡도나 실행된 조작수(통상적으로 O(x), x를 읽는 큰 O)와 연도의 교환수를 고려해야 한다.따라서 우리는 가장 자주 사용하는 방법을 되돌아보고 실현하며 그것들의 복잡성을 이해합시다.

기포 정렬

거품이 생기는 정렬의 작업 방식은 매우 간단하다.집합된 1항을 2항과 비교하다.첫 번째가 더 크면 두 개를 교환하세요.없으면 두 번째 항목으로 이동하여 동일한 작업을 반복합니다.우리는 목록의 끝에 도달할 때까지 이 점을 끊임없이 반복했다.
지금까지 우리는 목록에서 가장 큰 것을 맨 오른쪽에 놓았다.목록이 정렬될 때까지 나머지 항목에 대해 다시 이 동작을 반복합니다.
이 점을 살펴보자.

function bubbleSort(list) {
  let len = list.length;

  for(let i = len - 1; i >= 0; i--) {
    for(let j = 1; j <= i; j++) {
      if(list[j - 1] > list[j]) {
        let temp = list[j - 1];
        list[j - 1] = list[j];
        list[j] = temp;
      }    
    }  
  }

  return list;
}

bubbleSort([7, 5, 2, 3, 9, 6]); // [2, 3, 5, 6, 7, 9]

보시다시피 이 알고리즘은 가장 좋은 것이 아닙니다. 사실상 최악의 상황에서의 조작수로 볼 때 가장 무거운 알고리즘 중 하나입니다.그러나 유통기한을 넘기면 가장 좋은 유통기한 중 하나이다. 왜냐하면 그것은 이미 도착했기 때문이다.
최악의 경우 거품 정렬의 복잡도는 O(n2), 읽기big O of n square, 그중n은 집합 중의 항수이다.
그러나 가장 좋은 경우 (정렬된 집합) 는 O(n)와 O(1) 교환이 됩니다.
케이스
복잡성
최악의 성능
O(n2) 비교
O(n2) 교환
모범 사례 성능
O(n) 비교
O(1) 만료
평균 케이스 성능
O(n2) 비교
O(n2) 교환

정렬 선택

정렬과 거품 정렬을 선택하는 것은 매우 간단하다.우리는 목록을 훑어보고 최저 원소의 색인을 찾아서 최저 원소와 첫 번째 원소를 교환합니다.현재 첫 번째 항목이 정렬되었습니다. 우리는 모든 나머지 요소에 대해 이 동작을 반복합니다.
이 점을 살펴보자.

function selectionSort(list) {
  let minIndex, temp,
      len = list.length;

  for(let i = 0; i < len; i++) {
    minIndex = i;
    for(let j = i+1; j < len; j++) {
      if(list[j] < list[minIndex]) {
        minIndex = j;
      }
    }

    temp = list[i];
    list[i] = list[minIndex];
    list[minIndex] = temp;
  }

  return list;
}

selectionSort([11, 25, 12, 22, 64]); //[11, 12, 22, 25, 64]

위의 예제에서 목록이 매번 교체될 때마다 어떻게 정렬되는지 살펴보자.
정렬된 목록
정렬되지 않은 하위 목록
최소 요소
[]
[11, 25, 12, 22, 64]
십일
[11]
[25, 12, 22, 64]
십이
[11, 12]
[25, 22, 64]
22
[11, 12, 22]
[25, 64]
25
[11, 12, 22, 25]
[64]
64
[11, 12, 22, 25, 64]
[]
복잡성으로 말하자면, 우리가 어떤 상황에 직면하든지 간에 이 알고리즘은 변하지 않는다.여기서 O(n2)는 비교, O(n) 교환에 사용됩니다.그러나 만약 당신이 코드를 한 번 본다면, 그것은 스스로 해석한 것이다. 매우 간단하다. 때때로 우리는 이렇게 하려고 한다.기한을 넘기면 거품 순서보다 작다.
케이스
복잡성
최악의 성능
O(n2) 비교
O(n) 만료
모범 사례 성능
O(n2) 비교
O(n) 만료
평균 케이스 성능
O(n2) 비교
O(n) 만료

정렬 삽입하기

이것은 마치 내가 카드놀이를 할 때 누군가가 카드를 한 장 한 장 나에게 건네주는 것과 같다.나는 보통 그것들을 받을 때 순서대로 그것을 손에 넣는다.정렬을 삽입하여 한 번에 하나의 항목의 최종 목록을 생성합니다.이것은 경쟁사(예를 들어 빠른 정렬 또는 병합 정렬)에 비해 대형 목록에 대한 효율이 낮다는 것을 의미한다.
그러나 다음과 같은 몇 가지 이점이 있습니다.

간단한 실현.

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

기포 정렬 또는 선택 정렬보다 더 유효합니다.

자동 적응, 즉 정렬된 집합에 유효합니다.

도착.

온라인으로 목록을 받을 때 정렬할 수 있습니다.

어떻게 작동하는지 봅시다.

function insertionSort(list){
  let i, len = list.length, item, j;

  for(i = 1; i < len; i++){
    item = list[i];
    j = i;

    while(j > 0 && list[j-1] > item) {
      list[j] = list[j-1];
      j--;
   }

   list[j] = item;
  }

  return list;
}

복잡성의 경우 최악과 평균 상황에서 비교와 교환은 O(n2)의 거품 정렬과 유사하다.그러나 가장 좋은 상황에서 O(n) 비교와 O(1) 교환을 사용하는 것은 확실히 유효하다.
케이스
복잡성
최악의 성능
O(n2) 비교
O(n2) 교환
모범 사례 성능
O(n) 비교
O(1) 만료
평균 케이스 성능
O(n2) 비교
O(n2) 교환

병합 정렬

병합 정렬은 분치 알고리즘에서 귀속 모드로 이루어진다.우리는 명세서를 하나하나에 항목이 하나 있을 때까지 작은 덩어리로 분해했다.그리고 나서 우리는 그것들을 한데 합치지만, 그것들을 비교하고 항목을 순서대로 배열할 것이다.
이것은 정말 이해하기 쉽지만, 우리 그것의 실제 상황을 봅시다.

function mergeSort(list) {
   let len = list.length;
   if(len < 2)
      return list;
   let mid = Math.floor(len/2),
       left = list.slice(0,mid),
       right =list.slice(mid);

   return merge(mergeSort(left),mergeSort(right));
}

function merge(left, right) {
  let result = [],
      lLen = left.length,
      rLen = right.length,
      l = 0,
      r = 0;
  while(l < lLen && r < rLen) {
     if(left[l] < right[r]) {
       result.push(left[l++]);
     }
     else{
       result.push(right[r++]);
    }
  }  

  return result.concat(left.slice(l)).concat(right.slice(r));
}

이전의 알고리즘에 비해 합병 정렬은 복잡도 방면에서 훨씬 좋다.배열을 정렬하려면 O(n log n) 작업이 필요합니다.필요한 메모리에 대해 말하자면, 만약 우리가 수조를 사용한다면, O(n) 총계이며, O(n) 보조 항목이 있고, 우리가 체인 테이블을 사용한다면, O(1)이다.
케이스
복잡성
최악의 성능
O(n log n)
모범 사례 성능
O(n log n)
평균 케이스 성능
O(n log n)
최악 상황 공간
O(n) 총계, O(n) 목록 보조, O(1) 체인 테이블

빠른 정렬

빠른 정렬은 병합 정렬과 유사하지만, 다른 점은 우리가 집합을 둘로 나누지 않는다는 것이다.우리는 축의 중심점을 선택하고 거기에서 분할한다.일단 우리가 축심점을 선택한다면, 우리는 모든 비교적 작은 항목을 왼쪽에 놓고, 모든 비교적 큰 항목을 오른쪽에 놓는다.
이것은 축점 자체가 현재 정렬되었다는 것을 의미한다.전체 목록을 정렬할 때까지 왼쪽과 오른쪽에서 반복적으로 이 작업을 계속합니다.
선택 축은 무작위, 중간점, 목록의 첫 번째 항목 또는 마지막 항목이 될 수 있습니다.이 점을 할 수 있는 방법은 매우 많은데, 모든 방법에는 각자의 장단점이 있다.
그 차이를 더 잘 이해하기 위해 이 점을 살펴보자.

function quickSort(list, left, right) {
   let len = list.length, 
   pivot,
   partitionIndex;


  if(left < right) {
    pivot = right;
    partitionIndex = partition(list, pivot, left, right);

   //sort left and right
   quickSort(list, left, partitionIndex - 1);
   quickSort(list, partitionIndex + 1, right);
  }
  return list;
}

function partition(list, pivot, left, right) {
   let pivotValue = list[pivot],
       partitionIndex = left;

   for(let i = left; i < right; i++) {
    if(list[i] < pivotValue) {
      swap(list, i, partitionIndex);
      partitionIndex++;
    }
  }
  swap(list, right, partitionIndex);
  return partitionIndex;
}

function swap(list, i, j) {
   let temp = list[i];
   list[i] = list[j];
   list[j] = temp;
}

quickSort([11,8,14,3,6,2,7],0,6); 
//[2, 3, 6, 7, 8, 11, 14]

보시다시피 알고리즘의 효율이 높을수록 실현은 더욱 복잡합니다.복잡도로 말하자면, 최악의 경우, 그것은 합병 순서보다 가장 나쁘고, 평균치와 최적치에서 같다.
케이스
복잡성
최악의 성능
O(n2)
모범 사례 성능
단순 파티션이 있는 O(n log n), three-way partition가 있는 O(n)
평균 케이스 성능
O(n log n)
최악 상황 공간
O(n) 보조

무더기 정렬

무더기 정렬은 비교를 바탕으로 하는 정렬로 정렬을 선택하는 개선 버전으로 볼 수 있다.입력을 정렬 영역과 정렬되지 않은 영역으로 나눈 다음 최대 항목을 추출하여 정렬 영역에 삽입하여 정렬되지 않은 영역을 반복적으로 축소합니다.
정렬되지 않은 영역은 각 단계에서 가장 큰 항목을 더 빨리 찾을 수 있도록 heap data structure 에 유지됩니다.

💡 Since there is no heap data structure in JavaScript, we can use an array to represent it.

이것은 한 입입니다. 그 행동을 봅시다.

function heapSort(list) {
  let len = list.length;
  let i = Math.floor(len / 2 - 1);
  let j = len - 1;

  while(i >= 0) {
    heapify(list, len, i);

    i--;
  }

  while(k >= 0) {
    [list[0], list[k]] = [list[k], list[0]];

    heapify(list, k, 0);

    k--;
  }

  return list;
}

function heapify(list, len, i){   
  let largest = i;
  let left = i * 2 + 1;
  let right = left + 1;

  if(left < len && > list[left] > list[largest]) {
    largest = left;
  }

  if(right < len && list[right] > list[largest]) {
    largest = right;
  }

  if(largest != i) {
    [list[i], list[largest]] = [list[largest], list[i]];

    heapify(list, len, largest);
  }

  return list;
}

위의 코드 세그먼트에서 heapify 함수는 세 개의 원소, 부원소와 두 개의 서브원소를 비교했다.그리고 그것들의 최대 퇴적 순서가 정확한지 확인하세요. 왜냐하면 우리는 아래에서 위로 퇴적을 구축했기 때문입니다.
케이스
복잡성
최악의 성능
O(n log n)
모범 사례 성능
O(n log n)는 서로 다른 키이고, O(n)는 같은 키를 가지고 있다.
평균 케이스 성능
O(n log n)
최악 상황 공간
O(n) 총계, O(1) 보조

총결산

지금까지 당신은 이 정렬 알고리즘을 잘 이해했을 것입니다.만약 없다면, 나는 다시 한 번 보고 펜과 종이로 몇 가지 예를 써 보라고 건의한다.만약 무더기 정렬과 같은 더 복잡한 문제를 이해하는 데 어려움이 있다면, 걱정하지 마세요.이것은 전혀 문제없다. 왜냐하면 나도 처음에 같은 문제가 있었기 때문이다.그러나 실천과 시도를 통해 나는 마침내 이런 것을 배웠다.
다른 정렬 알고리즘도 많으니 마음대로 탐색하고 지금까지 배운 것과 작업 방식을 비교해 보세요.
당신의 소장품을 읽고 정리하는 것을 좋아해 주셔서 감사합니다.

⚡ All the images in this post are pulled from the algorithm's Wikipedia pages.