Implementacja metody .sort() w JavaScript

W poprzednim wpisie opisywałem zasadę działania metody .sort(). Teraz nadszedł czas na przemyślenia dotyczące samej implementacji. Postaram się pokazać w jaki sposób silnik JavaScript implementuje funkcje .sort(). To jeszcze lepiej pozwoli nam zrozumieć na jakiej zasadzie działa sortowanie elementów tablicy w JS.

Zanim przejdziemy do tematu zapoznaj się proszę z artykułem, o którym już wspominałem tj. Metoda .sort() w JavaScript jako wprowadzenie do programowania funkcyjnego. To pozwoli Ci lepiej zrozumieć o czym będę pisał i dodatkowo znajdziesz tam link do opisu algorytmy sortowania bąbelkowego, na którym oprę moją implementację.

Funkcjonalność dzięki prototypowaniu

Na początek stworzymy nową metodę .sort(), a w zasadzie nadpiszemy istniejącą wykorzystując prototypy (o nich również postaram się za jakiś czas napisać). Pamiętajmy, że jest ten wpis ma na celu zaprezentować możliwy sposób implementacji. Nie powinniśmy „przeciążać” istniejących metod dla standardowych obiektów dostępnych w JS – to raczej zawsze jest zły pomysł!

Array.prototype.sort = function(compareFn) {
    console.log('sort!');
}

var arr = [];
arr.push('d', 'a', 'b', 'c');
        
arr.sort(); // 'sort'

Powyższy kod spowoduje, że zamiast posortować naszą tablice, teraz w konsoli zobaczymy jedynie napis sort!. Nadszedł czas, aby zająć się implementacją algorytmu sortowania. Na razie nie przejmujemy się parametrem compareFn – to zostawimy na sam koniec.

Implementacja sortowania bąbelkowego

Array.prototype.sort = function(compareFn) {
    console.log('sort!');
    
    // ilość elementów w tablicy
    var len = this.length;
    
    // zmienne pomocnicze
    var i, j, tmp;
    
    for(j = 0; j < len - 1; j++) {
        for(i = 0; i < len - 1; i++) {
            // jeśli wartość elementu obecnego (i) jest większa
            // to zamien ich indeksy
            if(this[i] > this[i + 1]) {
                // tymczasowo przechowuje zawartość dla i
                tmp = this[i]; 
                this[i] = this[i + 1]; 
                this[i + 1] = tmp;
            };
        }
    }
}

var arr = [];
arr.push('d', 'a', 'b', 'c');
        
arr.sort();
console.log(arr); // ['a', 'b', 'c', 'd']

Pamiętając, że tworzymy metodę za pomocą prototype to this wskazuje na tablice, na której wywołaliśmy metodę .sort(). W naszym przypadku jest to cztero-elementowa tablica. Jak wiadomo właściwość length przechowuje informacje o ilości elementów w tablicy. My potrzebujemy tej danej, aby móc porównać każdy element ze sobą i w przypadku, gdy znajdziemy element [i] większy względem następnego [i+1] to zamieniamy je miejscem. Jest to najprostsza wersja implementacji algorytmu sortowania bąbelkowego.

Teraz wprowadźmy drobną modyfikację w linii 14:

Array.prototype.sort = function(compareFn) {
    console.log('sort!');
    
    // ilość elementów w tablicy
    var len = this.length;
    
    // zmienne pomocnicze
    var i, j, tmp;
    
    for(j = 0; j < len - 1; j++) {
        for(i = 0; i < len - 1; i++) {
            // jeśli wartość elementu obecnego (i) jest większa
            // to zamien ich indeksy
            if(this[i] - this[i + 1] > 0) {
                // tymczasowo przechowuje zawartość dla i
                tmp = this[i]; 
                this[i] = this[i + 1]; 
                this[i + 1] = tmp;
            };
        }
    }
}

var arr = [];
arr.push('d', 'a', 'b', 'c');
        
arr.sort();
console.log(arr); // ['a', 'b', 'c', 'd']

Zmiana dotyczyła warunku w pętli if, gdzie od obu stron odjąłem this[i+1] to pozwoliło mi uzyskać warunek w stylu: this[i] – this[i + 1] > 0. Co on oznacza? Jeśli różnica między [i]-tym elementem, a następnym [i+1]  jest większa od zera to zamień ich pozycję. Czy przypadkiem to nie jeden z warunków, które dotyczyły funkcji przekazywanej jako parametr? Przypomnę:

• jeśli zwróci wartość mniejszą od 0 – indeks elementu a będzie mniejszy niż indeks b,
• jeśli zwróci 0 – pozostawia a oraz b w niezmienionej kolejności względem siebie,
• jeśli zwraca wartość większą od 0 – indeks elementu a będzie większy niż indeks elementu b

Dwa pierwsze warunki nie powodują zmian dlatego nie musimy ich implementować. Skoro tak to może napiszemy prostą funkcję, którą wstawimy w miejsce warunku? Spróbujmy!

Array.prototype.sort = function(compareFn) {
    console.log('sort!');
    
    var compare = function(a, b) {
        return a > b ? 1 : 0;
    } 
    
    // ilość elementów w tablicy
    var len = this.length;
    
    // zmienne pomocnicze
    var i, j, tmp;
    
    for(j = 0; j < len - 1; j++) {
        for(i = 0; i < len - 1; i++) {
            // jeśli wartość elementu obecnego (i) jest większa
            // to zamien ich indeksy
            if(compare(this[i], this[i+1]) > 0) {
                // tymczasowo przechowuje zawartość dla i
                tmp = this[i]; 
                this[i] = this[i + 1]; 
                this[i + 1] = tmp;
            };
        }
    }
}

var arr = [];
arr.push('d', 'a', 'b', 'c');
        
arr.sort();
console.log(arr); // ['a', 'b', 'c', 'd']

Teraz mamy funkcję compare(), która ma dwa parametry tj. a i b. W naszym przypadku odpowiednio a => this[i], b => this[i+1]. Tak na prawdę nic się nie zmieniło tylko w warunku mamy funkcje, do której przekazujemy odpowiednie elementy tablicy. To prawda jednak dzięki temu rozwiązaniu tj. dostosowaniu go pod funkcje, możemy w to miejsce stawić dowolną funkcję, która będzie nas informować kiedy mamy przestawić indeksy.

Jeśli funkcja zwróci nam wartość większą od zera to wiemy, że musimy zmienić indeksy naszym wartością. Zobaczmy jak będzie wyglądał kod, który pozwoli nam dostosować nasze rozwiązanie pod dowolną funkcje. Zwróć jeszcze uwagę na to, że porównuję a > b. Jest to spowodowane tym, że ciągi znaków nie posiadają operatora różnicy więc stąd ten zapis.

Array.prototype.sort = function(compareFn) {
    console.log('sort!');
    
    var compare;
    if(typeof compareFn === 'function') {
        // jeśli parametrem jest funkcja to przypisz do compare
        compare = compareFn;
    } else {
        // jeśli nie to użyj domyślnej implementacji
        compare = function(a, b) {
            return a > b ? 1 : 0;
        }
    }
    
    // ilość elementów w tablicy
    var len = this.length;
    
    // zmienne pomocnicze
    var i, j, tmp;
    
    for(j = 0; j < len - 1; j++) {
        for(i = 0; i < len - 1; i++) {
            // jeśli wartość elementu obecnego (i) jest większa
            // to zamien ich indeksy
            if(compare(this[i], this[i+1]) > 0) {
                // tymczasowo przechowuje zawartość dla i
                tmp = this[i]; 
                this[i] = this[i + 1]; 
                this[i + 1] = tmp;
            };
        }
    }
}

var arr = [];
arr.push('d', 'a', 'b', 'c');
        
arr.sort();
console.log(arr); // ['a', 'b', 'c', 'd']
        
// przekazuje funkcję anonimową jako parametr
arr.sort(function(a, b){
    // definiuje odwrotną kolejność
    return b > a ? 1 : 0;
});
        
console.log(arr);  // ['d', 'c', 'b', 'a']

Teraz mamy już w pełni działające rozwiązanie. Oczywiście z powodu czytelności kodu uprościłem wiele rozwiązań jednak sam zamysł się nie zmienia. Mam nadzieje, że ten wpis wiele Ci wyjaśnił.