Algorithm_3. ツールバーの

コンセプト

ソートアルゴリズムは、ブラウズに使用するデータをリストすることを意味するコンピュータの分野で非常に重要な問題です.

O(n²) ツールバーの

泡の位置合わせ

Bubble sort(Bubble sort)は最も基本的で、最も低効率なソート方式であり、第1と第2、第2と第3...すべての要素を同じ方法で比較します.泡配列の時間的複雑度はO(n)であった.²)実際に使うことはほとんどないが,ソートアルゴリズムの基礎は主に学習のためである.

JavaScript

function bubbleSort(arr) {
  // i 번째로 큰 수가 i에 위치하게 된다.
  for (let i = 0; i < arr.length - 1; i++) {
    // 이미 정렬된 부분을 고려할 필요가 없으므로 - i 를 해준다
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
};

bubbleSort([4, 3, 2, 1]); // [1, 2, 3, 4]

[3,4,2,1]
[3,2,4,1]
[3,2,1,4]
[2,3,1,4]
[2,1,3,4]
[1,2,3,4]

パイ

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

コードを比較すると、Pythonの方が交換が容易であることがわかります.

カクテルのソート

気泡の並び替えを変えることで、偶数、奇数の開始方向が異なるカクテルの並び替え(カクテルの並び替え)もあります.

function cocktailSort(arr) {
  let min = 0;
  let max = arr.length - 1;
  let swapped = true;

  while (swapped) {
    swapped = false;

    // 왼쪽에서 오른쪽으로 커지는 버블정렬
    for (let i = min; i < max; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
    max--;

    if (!swapped) {
      break; // 이미 정렬되어 있는 경우 탈출
    }

    swapped = false;

    // 오른쪽에서 왼쪽으로 작아지는 버블정렬
    for (let i = max; i > min; i--) {
      if (arr[i - 1] > arr[i]) {
        let temp = arr[i];
        arr[i] = arr[i - 1];
        arr[i - 1] = temp;
        swapped = true;
      }
    }
    min++;
  }
  return arr;
}

cocktailSort([4, 3, 2, 1]);  // [1, 2, 3, 4]

[3,2,1,4]
[1,3,2,4]
[1,2,3,4]

ソートの選択

すぐに比較と置換を繰り返すBubbleソートとは異なり、「ソート」(Selection sort)を選択して最小要素から最後までブラウズし、順番にソートします.これは人間の考え方に最も似たソート方式と見なすことができ、Bubbleソートより約2倍速い.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++){
  let smallestIdx = i
    // 가장 작은 요소의 인덱스 탐색
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[smallestIdx] > arr[j]) {
        smallestIdx = j;
      }
    }
    
    // 현재 요소(arr[i])가 가장 작은 요소가 아니라면 스왑
    if (arr[i] > arr[smallestIdx]) {
       let temp = arr[i];
       arr[i] = arr[smallestIdx];
       arr[smallestIdx] = temp;
    }
  }
  return arr;
}

selectionSort([4, 3, 2, 1]);  // [1, 2, 3, 4]

[1, 3, 2, 4]
[1, 2, 3, 4]

整列挿入

挿入ソート(Insertionsort)は、残りの材料を伸ばすように要素をソートし、適切な位置に挿入します.配列の大きさが小さいと、効果的に働きます.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i]; // 현재값 저장
    let j = i - 1; // 정렬된 부분의 현재 인덱스
    
    // 좌측 값이 현재 값보다 크다면 스왑
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current; // 현재값을 정렬된 인덱스에 할당
  }
  return arr;
}

insertionSort([4, 3, 2, 1]);  // [1, 2, 3, 4]

[3, 4, 2, 1]
[2, 3, 4, 1]
[1, 2, 3, 4]

O(n log n)ソート

連結ソート

マージソート(Merge sort)は典型的な分割征服アルゴリズムであり,ジョン・フォンノイマンによって開発された.1つの要素の個数を1または0になるまで半減し、カット順の逆の順序でサイズを比較してマージします.この統合ソートの利点は、안정 정렬が大量のメモリを必要とするが、データ状態の影響を受けないことである.

function mergeSort(arr) {
  if (arr.length < 2) return arr; // 원소가 하나일 때는 그대로
  let pivot = Math.floor(arr.length / 2); 
  let left = arr.slice(0, pivot); 
  let right = arr.slice(pivot, arr.length); 
  return merge(mergeSort(left), mergeSort(right)); 
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) { // 두 배열의 첫 원소를 비교하여
      result.push(left.shift()); // 더 작은 수를 결과에 push
    } else {
      result.push(right.shift()); // 오른쪽도 마찬가지
    }
  }
  while (left.length) result.push(left.shift()); // 어느 한 배열이 더 많이 남았다면 나머지 모두 push
  while (right.length) result.push(right.shift()); // 오른쪽도 마찬가지
  return result;
};

mergeSort([4, 3, 2, 1]); // [1, 2, 3, 4]

[4, 3] [2, 1]
[4], [3], [2], [1]
[3, 4] [1, 2]
[1, 2, 3, 4]

クイックソート

クイックソート(Quick sort)は、比較演算子のソート方式で最も性能の高いアルゴリズムであり、適切な基準(pivot)要素を設定し、基準より大きい場合に後方、後方または前方に送信する操作を繰り返してソートする.ただし、設定基準の方式によっては性能の差が大きいため、ランダム設定基準のランダムクイックソート方式や、複数のソートアルゴリズムを用いたハイブリッドクイックソートなどが用いられる場合がある.
クイックソートは分割方式によってLomuto's Partition SchemeとHoare's Partition Schemeに分けられる.

Lomuto’s Partition Scheme

function Swap(array, position1, position2) {
  let temp = array[position1];
  array[position1] = array[position2];
  array[position2] = temp;
}
  
function partition(arr, low, high) {
  let pivot = arr[high];
  let i = (low - 1);
  
  for (let j = low; j <= high- 1; j++) {
    if (arr[j] <= pivot) {
      i++; 
      Swap(arr, i, j);
    }
  }
  Swap(arr, i + 1, high);
  return (i + 1);
}
  
function quickSort(arr, low, high) {
  if (low < high) {
    let pi = partition(arr, low, high) 
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
  }
  return arr;
}

quickSort(arr, 0, arr.length-1);

Hoare’s Partition Scheme

function partition(arr, low, high) {
  let pivot = arr[low];
  let i = low - 1, j = high + 1;
  
  while (true) {
    do { 
      i++; 
    } while (arr[i] < pivot);
  
    do {
      j--;
    } while (arr[j] > pivot);
  
  if (i >= j) return j;
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
  
function quickSort(arr, low, high) {
  if (low < high) {
    let pi = partition(arr, low, high);
      quickSort(arr, low, pi);
      quickSort(arr, pi + 1, high);
  }
  return arr;
}
  
quickSort(arr, 0, arr.length - 1);

ブレンド位置合わせ(Blend Align)

ソートチーム

チームソート(Tim sort)は、マージソートと挿入ソートの組み合わせであり、2002年にTim PetersがPythonのために開発された.したがって、Pythonのソート()の大部分は、最も速い速度でソートを実行することができる.チーム・ソートは、ほとんどのデータがソートされているという仮定に基づいて、集計ソートを使用してソートされますが、要素の数が少ない場合はオーバーヘッドが発生するため、パーティション・サイズが値(通常16または32)未満の場合は、ソートを挿入してソートされます.

安定ソートvs不安定ソート

ソース:Tim sortについて
上記の表に示すように,ソートアルゴリズムは基本的に安定ソートと不安定ソートに分けられる.安定したソートは、入力順序と同じ値を繰り返すソートであり、任意のデータを時間順にソートし、地域名順に並べ替えると、ソートは元の順序を維持します.ただし、不完全なソートは、再ソート時に既存のソート順を無視してすべてブレンドされます.この不完全なソートの典型的な例は、入力値の形式によって速度が急激に変化するため、性能が不均一であるという欠点を有する高速ソートである.
リファレンス
ソートアルゴリズム
Tim sortについて
Pythonアルゴリズムインタビュー
Hoare’s vs Lomuto partition scheme in QuickSort