W języku JavaScript mamy wiele wbudowanych metod, z których możemy dowolnie korzystać na odpowiednio przekazanych do nich zbiorze danych. Jednak gdy chcemy wykonać bardziej skomplikowane operacje musimy przygotować odpowiednią funkcję. Aby funkcja ta działała jak najoptymalniej warto znać i potrafić wykorzystać istniejące od wielu lat rozwiązania pewnych operacji na zbiorze danych. Tymi rozwiązaniami są szeroko pojęte algorytmy wraz z wspierającymi je strukturami danych.
Możliwe, że na co dzień w pracy frontend developera nie będą one nam potrzebne ale warto jest poznać choćby z racji tego, że często są to elementy zadań rekrutacyjnych do firm.
W tej serii wpisów chciałbym skupić się na nie tylko algorytmie ale także na kodzie pisanym za pomocą TypeScriptu. Tego w jaki sposób możemy wykorzystać interfejsy, dziedziczenie czy to jak wpływa rodzaj klas przez nas wykorzystywany.
Algorytm sortowania bąbelkowego.
Przechodząc do głównego tematu. Zadaniem tego wpisu będzie stworzenie algorytmu sortującego bąbelkowo elementy przekazane w tablicy. Poniższy kod przedstawia wyniki sortowania po przekazaniu to funkcji pewnych argumentów.
const randomNumbers = [11, -90, 0, 123, 15]
bubbleSort(randomNumbers) // => [-90, -11, 0, 15, 123]
const randomCharacters = 'aZaaBy'
bubbleSort(randomCharacters) // => 'aaaByZ'
Sortowanie bąbelkowe działa w następujący sposób: porównywane są sąsiadujące indeksy elementów zawartych w tablicy. Na przykładzie z liczbami zawartymi w tablicy algorytm bierze pierwszy element czyli 11 i porównuje go z drugim, który wynosi -90. Jeżeli pierwszy element jest większy od drugiego to zamieniają się one miejscami. Następnie przeniesiony na drugie miejsce element z numerem 11 jest porównywany z elementem z indeksem numer trzy czyli 0. Następuje te same porównanie i tym razem także następuje zamiana miejsc.
Algorytm w ten sposób iteruje po wszystkich elementach przekazanej tablicy a w rezultacie otrzymujemy posortowaną od najmniejszej do największej liczby tablicę.
W drugim przykładzie sytuacja jest nie co inna. Wszystko dzieje się za sprawą JavaScriptu oraz jego sposobu zapisu elementów o typie string.
Gdy porównamy dwa elementy takie jak 'Y' > 'a' otrzymamy wynik false. Dzieje się to przez fakt, że w zasadzie JavaScript nie porównuje bezpośrednio stringów a sprawdza on jaki posiadają one indeks.
'Y'.charCodeAt()
=> 89
'a'.charCodeAt()
=> 97
W powyższym przypadku Y ma mniejszy indeks niż a co potwierdza otrzymany wynik (tablicę znaków i ich indeksów znajduje się tutaj: http://www.asciitable.com/). Tworzy nam to pewien problem w kontekście budowy algorytmu jednak jesteśmy w stanie go obejść co zaprezentuje w dalszej części tego wpisu.
Tworzenie algorytmu.
Na początku stworzymy najprostszą implementację algorytmu, która będzie obsługiwała podmianę liczb w tablicy oraz ustawienie ich w odpowiednie miejsca. Do tego celu stworzyć musimy plik, w którym zawarta będzie cała logika.
// BubbleSorter.ts
class BubbleSorter {
constructor(public collection: number[]) {}
sortElements(): void {
}
}
const numbersToSort = new BubbleSorter([3, -5, 12, 1, 10]);
numbersToSort.sort(); // => [-5, 1, 3, 10, 12]
// collection: number[];
//
// constructor(collection: number[]) {
// this.collection = collection;
// }
Na początku stworzona została klasa o nazwie BubbleSorter, która przy stworzeniu instancji klasy wymagać będzie elementu o nazwie collection, który musi się składać z tablicy liczb. Dodatkowo w powyższym bloku zawarty został kod, którego element konstruktora jest odpowiednikiem elementu zadeklarowanego bezpośrednio jako public.
Klasę mamy już stworzoną więc musimy teraz zaimplementować logikę sortującą.
// BubbleSorter.ts
sortElements(): void {
const { length } = this.collection;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - i - 1; j++) {
if (this.collection[j] > this.collection[j + 1]) {
const leftHandValue = this.collection[j];
this.collection[j] = this.collection[j+1];
this.collection[j + 1] = leftHandValue;
}
}
}
}
Pierwszym elementem jest wyciągnięcie informacji o długości tablicy na której przeprowadzana jest operacja sortowania. Przy pomocy destrukturyzacji zostało to zaimplementowane poprzez const { length } = this.collection.
Kolejnymi elementami jest stworzenie zagnieżdżonych pętel for. Pierwsza iteruje długości tablicy. Druga natomiast robi to samo jednak w drugim wyrażeniu j < length - i -1 sprawia, że przy pierwszym uruchomieniu pętli drugi porównywany element znajdzie się w poprawnym miejscu. Sprawia to, że nie będziemy musieli drugi raz sortować tego elementu w przyszłości.
Wewnątrz drugiej pętli mamy już logikę odpowiadającą za przestawianie elementów w tablicy. Pierwszy if sprawdza czy indeks danej operacji pętli jest większy od następnego. Przykładowo przy drugiej iteracji na tablicy [1, -1, 5, 0] będzie sprawdzane czy -1 jest większe od 5. Jeżeli te sprawdzenie okaże się prawdą a naszym przykładzie tak jest to następuje wykonanie kodu wewnątrz tego sprawdzenia.
Na początku inicjalizowana jest zmienna leftHandValue, do której przypisana zostaje wartość kolekcji danej iteracji. Następnie do wartości elementu collection [j] przypisana zostaje wartość [j+1]. W ostatniej linicje zostaje przypisana wartość leftHandValue dla elementu collection [j+1]. Aby łatwiej było zrozumieć kod weźmy z powrotem przykład tablicy [1, -1, 5, 0] oraz jej drugiej iteracji. Jako collection [j] mamy liczbę -1 a jako collection [j +1] liczbę 5. Możemy uznać że -1 jest wartością leftHandSide a 5 rightHandSide.
// BubbleSorter.ts
class BubbleSorter {
constructor(public collection: number[]) {}
sortElements(): void {
const { length } = this.collection;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - i - 1; j++) {
if (this.collection[j] > this.collection[j + 1]) {
const leftHandValue = this.collection[j];
this.collection[j] = this.collection[j+1];
this.collection[j + 1] = leftHandValue;
}
}
}
}
}
const numbersToSort = new BubbleSorter([3, -5, 12, 1, 10]);
numbersToSort.sort(); // => [-5, 1, 3, 10, 12]
W ten sposób ostatecznie prezentuje się implementacja sortowania bąbelkowego. Jednak musimy wprowadzić tutaj kilka zmian aby była możliwość sortowania ciągów znaków.
Ważnym elementem jest świadomość tego, że JavaScript pozwala nam podejrzeć wartość wybranego indeksu z ciągu znaków. Jednak jego podmiana zakończy się niepowodzeniem.
const animal = 'cat'
animal[0] // 'c'
animal[0] = 'b'
animal // => 'cat'
Oznacza to, że logika podmiany wartości indeksów nie będzie działała na przekazanych ciągach znaków. Dodatkowo sprawdzenie za pomocą polecenia if także nie zadziała o czym już wcześniej wspominałem w tym wpisie.
Refaktoryzacja.
Aby osiągnąć zamierzony efekt czyli możliwość sortowania tablic liczb oraz ciągów znaków musimy przeprowadzić refaktoryzacje klasy BubbleSorter. W jej konsekwencji otrzymamy trzy klasy. Będą to BubbleSorter, NumbersCollection oraz CharactersCollection.
Klasy NumbersCollection oraz CharactersCollection będą posiadały logikę odpowiadającą za podmianę elementów tablicy lub ciągu znaków, porównanie elementów oraz sprawdzenie długości tablicy lub ciągu znaków.
Logika w obu klasach będzie się nieco różniła z racji problemów wynikających z sortowaniem znaków w JavaScript.
Zajmijmy się najpierw przeniesieniem logiki z klasy BubbleSorter do NumbersCollection.
// NumbersCollection.ts
export class NumbersCollection {
constructor(public data: number[]) {};
get length(): number {
return this.data.length;
}
compare(leftIndex: number, rightIndex: number): boolean {
return this.data[leftIndex] > this.data[rightIndex]
}
swap(leftIndex: number, rightIndex: number): void {
const leftHand = this.data[leftIndex];
this.data[leftIndex] = this.data[rightIndex];
this.data[rightIndex] = leftHand;
}
}
Refaktoryzacja przebiegła w następujący sposób. Stworzone zostały trzy funkcje pomocniczne wewnątrz klasy. Pierwsza z nich odpowiada za pobranie długości tablicy na której przeprowadzona będzie operacja sortowania.
Funkcja compare będzie wykorzystana w operacji sprawdzającej if w naszym BubbleSorterze.
Ostatnia funkcja swap odpowiada za logikę, która znajdowała się wewnątrz sprawdzenia if. Podmienia ona elementy w danych indeksach gdy sprawdzenie if okaże się prawdziwe.
Aby teraz wykorzystać metody z tej klasy należy zaimportować NumbersCollection do klasy BubbleSorter.
// BubbleSorter.ts
import { NumbersCollection } from './NumbersCollection';
class BubbleSorter {
constructor(public collection: NumbersCollection) {}
sortElements(): void {
const { length } = this.collection;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - i - 1; j++) {
if (this.collection.compare(j, j + 1)) {
this.collection.swap(j, j + 1);
}
}
}
}
}
const numbersToSort = new NumbersCollection([3, -5, 12, 1, 10]);
const bubbleSorter = new BubbleSorter(numbersToSort);
bubbleSorter.sort(); // => [-5, 1, 3, 10, 12]
W klasie BubbleSorter należy w konstruktorze wykorzystać NumbersCollection jako instancje naszej kolekcji (collection).
Następnie już w samej logice wykorzystać funkcję compare() zawartą w naszej instancji oraz swap(). Obydwu funkcją przekazujemy te same argumenty czyli j - aktualny indeks pętli for oraz jej kolejny indeks czyli j + 1.
Podsumowanie
W tym wpisie zakończymy pracę nad algorytmem i będziemy kontynuować ją w kolejnym. Dowiedzieliśmy się jednak to czym właściwie jest algorytm sortowania bąbelkowego, jak go zaimplementować w TypeScripcie oraz dlaczego praca na elementach typu string jest czasami problematyczna.