Implementacja JavaScript Array.sort?

Z jakiego algorytmu Array#sort()korzysta funkcja JavaScript ? Rozumiem, że wykonywanie różnego rodzaju argumentów może wymagać wielu argumentów i funkcji, po prostu interesuje mnie, jakiego algorytmu używa sortowanie waniliowe.

Jeśli spojrzysz na ten błąd 224128 , wygląda na to , że Mozilla używa MergeSort.

Właśnie obejrzałem źródło WebKit (Chrome, Safari…) . W zależności od rodzaju tablicy stosowane są różne metody sortowania:

Tablice numeryczne (lub tablice typu pierwotnego) są sortowane przy użyciu standardowej funkcji bibliotecznej C ++, std::qsortktóra implementuje pewną odmianę szybkiego sortowania (zwykle wewnątrz sortowania ).

Przylegające tablice nieliczbowego typu są uszeregowane i sortowane przy użyciu funkcji scalesort, jeśli są dostępne (w celu uzyskania stabilnego sortowania) lub qsortjeśli nie jest dostępne sortowanie metodą scalania.

W przypadku innych typów (tablic niesąsiadujących i przypuszczalnie w przypadku tablic asocjacyjnych) WebKit używa sortowania selekcyjnego (które nazywają sortowaniem „min” ) lub, w niektórych przypadkach, sortuje za pomocą drzewa AVL. Niestety, dokumentacja tutaj jest raczej niejasna, więc trzeba by prześledzić ścieżki kodu, aby zobaczyć, dla których typów jest używana metoda sortowania.

A potem są klejnoty takie jak ten komentarz :

// 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).

- Miejmy tylko nadzieję, że ktokolwiek „naprawi” to, lepiej rozumie asymptotyczne środowisko wykonawcze niż autor tego komentarza i zdaje sobie sprawę, że sortowanie radix ma nieco bardziej złożony opis środowiska wykonawczego niż po prostu O (N).

(Podziękowania dla phsource za wskazanie błędu w oryginalnej odpowiedzi.)

JS nie ma wstępnego wymogu używania określonego algorytmu sortowania. Jak wielu wspomniało tutaj, Mozilla używa sortowania korespondencji seryjnej, jednak w kodzie źródłowym Chrome v8 na dzień dzisiejszy używa QuickSort i InsertionSort, dla mniejszych tablic.

Źródło silnika V8

Z linii 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;
      }
    }
  };

Aktualizacja Od 2018 roku V8 używa TimSort, dzięki @celwell. Źródło

Standard ECMAscript nie określa, który algorytm sortowania należy zastosować. Rzeczywiście, różne przeglądarki mają różne algorytmy sortowania. Na przykład metoda sort () Mozilla / Firefox nie jest stabilna (w sensie sortowania tego słowa) podczas sortowania mapy. IE sort () jest stabilny.

Po dalszych badaniach okazało się, że w przypadku Mozilla / Firefox Array.sort () używa scalesort. Zobacz kod tutaj .

Myślę, że to zależy od implementacji przeglądarki, o której mowa.

Każdy typ przeglądarki ma własną implementację silnika javascript, więc to zależy. Możesz sprawdzić repozytorium kodu źródłowego dla Mozilli i Webkit / Khtml dla różnych implementacji.

IE jest jednak źródłem zamkniętym, więc być może będziesz musiał zapytać kogoś w Microsoft.

Począwszy od wersji V8 7.0 / Chrome 70, wersja V8 używa TimSort , algorytmu sortowania Pythona. Chrome 70 został wydany 13 września 2018 r.

Zobacz post na blogu deweloperów V8, aby uzyskać szczegółowe informacje na temat tej zmiany. Możesz także odczytać kod źródłowy lub poprawkę 1186801 .

Funkcja Array.sort () JavaScript ma wewnętrzne mechanizmy wyboru najlepszego algorytmu sortowania (QuickSort, MergeSort itp.) Na podstawie typu danych elementów tablicy.

spróbuj tego z szybkim sortowaniem:

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);
}