Implementasi Javascript Array.sort?

Algoritme manakah yang Array#sort()digunakan fungsi JavaScript ? Saya mengerti bahwa itu bisa mengambil segala macam argumen dan fungsi untuk melakukan berbagai macam jenis, saya hanya tertarik pada algoritma yang menggunakan jenis vanilla.

Jika Anda melihat bug ini 224128 , tampaknya MergeSort sedang digunakan oleh Mozilla.

Aku baru saja melihat pada WebKit (Chrome, Safari ...) sumber . Bergantung pada jenis array, berbagai metode sortir digunakan:

Array angka (atau array tipe primitif) diurutkan menggunakan fungsi pustaka standar C ++ std::qsortyang mengimplementasikan beberapa variasi quicksort (biasanya introsort ).

Array yang bersebelahan dari tipe non-numerik dirangkai dan diurutkan menggunakan mergesort, jika tersedia (untuk mendapatkan pengurutan yang stabil) atau qsortjika tidak ada pengurutan gabungan yang tersedia.

Untuk tipe lain (array yang tidak bersebelahan dan mungkin untuk array asosiatif) WebKit menggunakan salah satu jenis seleksi (yang mereka sebut semacam "min" ) atau, dalam beberapa kasus, itu mengurutkan melalui pohon AVL. Sayangnya, dokumentasi di sini agak kabur sehingga Anda harus melacak jalur kode untuk benar-benar melihat jenis metode yang digunakan.

Dan kemudian ada permata seperti komentar ini :

// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).

- Mari kita berharap bahwa siapa pun yang benar-benar "memperbaiki" ini memiliki pemahaman yang lebih baik tentang runtime asimptotik daripada penulis komentar ini, dan menyadari bahwa radix sort memiliki deskripsi runtime yang sedikit lebih kompleks daripada hanya O (N).

(Terima kasih kepada phsource karena menunjukkan kesalahan dalam jawaban aslinya.)

Tidak ada persyaratan wajib bagi JS untuk menggunakan algorthim penyortiran tertentu. Seperti banyak yang telah disebutkan di sini, Mozilla menggunakan semacam gabungan. Namun, dalam kode sumber Chrome v8, mulai hari ini, ia menggunakan QuickSort dan InsertionSort, untuk array yang lebih kecil.

Sumber Mesin V8

Dari Garis 807 - 891

  var QuickSort = function QuickSort(a, from, to) {
    var third_index = 0;
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
      }
      if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
      } else {
        third_index = from + ((to - from) >> 1);
      }
      // Find a pivot as the median of first, last and middle element.
      var v0 = a[from];
      var v1 = a[to - 1];
      var v2 = a[third_index];
      var c01 = comparefn(v0, v1);
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1.
      var c02 = comparefn(v0, v2);
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
        var c12 = comparefn(v1, v2);
        if (c12 > 0) {
          // v0 <= v2 < v1
          var tmp = v1;
          v1 = v2;
          v2 = tmp;
        }
      }
      // v0 <= v1 <= v2
      a[from] = v0;
      a[to - 1] = v2;
      var pivot = v1;
      var low_end = from + 1;   // Upper bound of elements lower than pivot.
      var high_start = to - 1;  // Lower bound of elements greater than pivot.
      a[third_index] = a[low_end];
      a[low_end] = pivot;

      // From low_end to i are elements equal to pivot.
      // From i to high_start are elements that haven't been compared yet.
      partition: for (var i = low_end + 1; i < high_start; i++) {
        var element = a[i];
        var order = comparefn(element, pivot);
        if (order < 0) {
          a[i] = a[low_end];
          a[low_end] = element;
          low_end++;
        } else if (order > 0) {
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = comparefn(top_elem, pivot);
          } while (order > 0);
          a[i] = a[high_start];
          a[high_start] = element;
          if (order < 0) {
            element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
          }
        }
      }
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
    }
  };

Pembaruan Pada 2018 V8 menggunakan TimSort, terima kasih @celwell. Sumber

Standar skrip ECMA tidak menentukan algoritma pengurutan mana yang akan digunakan. Memang, browser yang berbeda menampilkan algoritma pengurutan yang berbeda. Misalnya, sortir () Mozilla / Firefox tidak stabil (dalam arti kata sortir) saat menyortir peta. Semacam IE () stabil.

Setelah beberapa penelitian lebih lanjut, tampaknya, untuk Mozilla / Firefox, Array.sort () menggunakan mergesort. Lihat kodenya di sini .

Saya pikir itu akan tergantung pada implementasi browser apa yang Anda maksud.

Setiap jenis browser memiliki implementasi mesin javascript sendiri, jadi itu tergantung. Anda dapat memeriksa repos kode sumber untuk Mozilla dan Webkit / Khtml untuk implementasi yang berbeda.

IE adalah sumber tertutup, jadi Anda mungkin harus bertanya kepada seseorang di microsoft.

Pada V8 v7.0 / Chrome 70, V8 menggunakan TimSort , algoritma penyortiran Python. Chrome 70 dirilis pada 13 September 2018.

Lihat posting di blog dev V8 untuk detail tentang perubahan ini. Anda juga dapat membaca kode sumber atau tambalan 1186801 .

Fungsi JavaScript Array.sort () memiliki mekanisme internal untuk memilih algoritma penyortiran terbaik (QuickSort, MergeSort, dll.) Berdasarkan tipe data elemen array.

coba ini dengan sortir cepat:

function sort(arr, compareFn = (a, b) => a <= b) {

    if (!arr instanceof Array || arr.length === 0) {
        return arr;
    }

    if (typeof compareFn !== 'function') {
        throw new Error('compareFn is not a function!');
    }

    const partition = (arr, low, high) => {
        const pivot = arr[low];
        while (low < high) {
            while (low < high && compareFn(pivot, arr[high])) {
                --high;
            }
            arr[low] = arr[high];
            while (low < high && compareFn(arr[low], pivot)) {
                ++low;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    };

    const quickSort = (arr, low, high) => {
        if (low < high) {
            let pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
        return arr;
    };

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