✅ Proste algorytmy sortowania JavaScript

Spisie treści

Algorytm jest z definicji uporządkowanym zbiorem (To jest bardzo ważne) systematycznych operacji, które pozwalają nam wykonać obliczenia, aby znaleźć rozwiązanie wszystkich problemów tego samego typu. Innymi słowy, jest to zestaw instrukcji, które zawsze są zgodne z następującym wzorcem:

Precyzja: Musisz jednoznacznie i jednoznacznie wyjaśnić każdy krok lub instrukcję.
Skończone: Liczba instrukcji do wykonania musi być ograniczona.
Definicja: Te same dane wejściowe muszą zawsze zapewniać te same informacje wyjściowe.
Wejście: Liczba elementów wejściowych może wynosić zero lub więcej.
Rezolucja: Powinien zawsze dawać wynik, który będzie danymi wyjściowymi.

Kiedy algorytm jest zaimplementowany w określonym języku programowania, staje się programem, który można wykonać na komputerze, dlatego możemy powiedzieć, że program jest algorytmem lub zbiorem algorytmów napisanych w określonym języku, które komputer może zinterpretować. W tym przypadku program ten nazywa się algorytmem obliczeniowym. Z drugiej strony, jeśli nie potrzebuje komputera do działania, mówimy o algorytmach nieobliczeniowych.

W naszym przypadku będziemy rozmawiać algorytmy obliczeniowe.

Wiedząc, czym jest algorytm, skupimy się na algorytmach sortujących, czyli algorytmie służącym do sortowania i zwracania listy, która została wstępnie zaopatrzona w losowo ułożone elementy, które są już uporządkowane.
ten 3 algorytmy sortowania najbardziej znane są Sortowanie bąbelkowe lub sortowanie według bąbelków, Sortowanie przez zaznaczenie lub sortowanie według zaznaczenia oraz Sortowanie przez wstawianie lub sortowanie według wstawienia. Wszystkie są uważane za proste algorytmy lub metody, ponieważ są rozwiązywane przez iterację lub powtórzenie do n razy.

1. Sortowanie bąbelkowe lub sortowanie według bąbelkówBiorąc jako przykład tablicę z czterema wartościami, w tym przypadku dla uproszczenia cztery liczby, zobaczymy, jak działa algorytm.

Tablica = (4, 7, 8, 5, 9);

Chcemy, abyś zwrócił go w kolejności od najwyższego do najniższego, czyli (9, 8, 7, 5, 4).

Aby to zrobić, pierwszą rzeczą, którą musimy zrobić, to zapytać o dwie pierwsze wartości, która jest największa. W przypadku, gdy druga wartość jest większa od pierwszej tak jak ma to miejsce należy je wymienić, natomiast jeśli są już zamówione to zostawiamy je bez zmian.
Następnie ten sam proces musiałby zostać powtórzony z drugą i trzecią wartością. W tym przypadku trzecia wartość jest większa, więc zamienilibyśmy ją zostawiając naszą tablicę = (7, 8, 4, 5, 9).
Następnie powtarzamy poprzedni krok z trzecią i czwartą wartością i ponownie je wymieniamy. (7, 8, 5, 4, 9).
I wreszcie po pierwszej iteracji będzie to: (7, 8, 5, 9, 4).
Nadal nie jest uporządkowany, jednak osiągnięto, że ostatni element, ten po prawej stronie całości, to 4, jeśli jest uporządkowany jako najmniejsza ze wszystkich.
W kolejnej rundzie, aby uporządkować naszą tablicę, nie trzeba już brać pod uwagę ostatniego, ponieważ wiemy już, że jest on uporządkowany, więc porównalibyśmy pierwszy i drugi element, potem drugi i trzeci element, a na końcu trzeci i czwarty element, a tablica pozostanie: (8, 7, 9, 5, 4).
Teraz sortowany jest ostatni i przedostatni element.
Wykonujemy kolejną rundę porównując pierwszą i drugą wartość a potem drugą i trzecią i tablica wygląda tak: (8, 9, 7, 5, 4).
Ostatnie trzy elementy są już uporządkowane, więc wystarczy jeszcze jedna kolejka, aby całkowicie uporządkować tablicę: (9, 8, 7, 5, 4).

W ten sposób algorytm burburja, co jest tak zwane, ponieważ w każdej turze ostatni element unosi się jak bańka i jest uporządkowany.

Teraz wdrożone do JavaScript To bardzo proste:

funkcja bubble (myArray) {var tam = mojaTablica.length; for (var temp = 1; temp <rozmiar; temp ++) {for (var left = 0; left <(rozmiar - temp); left ++) {var right = left + 1; if (myArray [left] <myArray [right] {sort (myArray, left, right);}}} return mojaTablica;}

Przekazujemy tablicę do naszej funkcji i w jej ramach pierwszą rzeczą, którą robimy, jest obliczenie jej rozmiaru, obliczenie liczby elementów w tablicy.
Następnie tworzymy zewnętrzną pętlę, która przechodzi przez naszą tablicę tyle razy, ile elementów ma minus jeden (bo są to czasy niezbędne do całkowitego uporządkowania).
Wewnętrznie tworzymy kolejną pętlę, która przechodzi przez wartości porównując każdą z następną i jeśli ta po lewej jest mniejsza niż ta po prawej, wymienia je z funkcją sort, którą zobaczymy dalej.
W końcu zwraca uporządkowaną tablicę.

sortowanie funkcji (mojatablica, wartość1, wartość2) {zmienna temp = mojatablica [wartość1]; mojaTablica [wartość1] = mojaTablica [wartość2]; mojaTablica [wartość2] = temp; zwróć moją tablicę;}

gdzie wartość1 jest indeksem pierwszego przedmiotu do wymiany, a wartość2 jest indeksem drugiego przedmiotu do wymiany.

2. Sortowanie wyboruAlgorytm, który zobaczymy poniżej nie przesuwa elementów jeden po drugim jak w bańce jeden, ale najpierw przechodzi przez całą tablicę, a następnie wybiera właściwy element do umieszczenia według kryteriów, którymi się kierujemy (np. od najwyższego do najniższego) i umieszcza go bezpośrednio w swojej pozycji, i tak algorytm otrzymuje swoją nazwę, wybierając, biorąc element i przesuwając go jednym ruchem do właściwej pozycji.

W tym samym przykładzie co poprzednio Array = (4, 7, 8, 5, 9), jeśli chcemy np. uporządkować ją od najwyższego do najniższego, najpierw wybralibyśmy 9 i umieścili na pierwszym miejscu, a 4 zajęłoby ostatnie pozycja (9, 7, 8, 5, 4). W drugiej rundzie wybrał 8 i zamienił się z 7, aby pozostać na właściwej pozycji. W kolejnych rundach nie zmieniłbym niczego, ponieważ zostało to już zamówione.

Kod tego algorytmu wyglądałby następująco:

wybór funkcji (myArray) {var tam = mojaTablica.length; for (var temp = 0; temp <rozmiar -1; temp ++) {główny = temp; for (var check = temp + 1; check <size; check ++) {if (myArray [check] <myArray [major] {major = check;}} sort (myArray, major, check);} return myArray;}

Kod działa podobnie jak w bańce, ale zewnętrzna pętla for przechodzi przez wartości od 0 do N-2 (są to tyle samo kroków co między 1 a N-1 jak w bańce, ale działanie jest inne ) operując bezpośrednio na elementach, aby przy każdym obrocie ustawić je we właściwej pozycji.
Liczba tur potrzebnych do zamówienia wszystkich elementów jest taka sama jak w bańce N-1, ponieważ po każdej iteracji zostawiamy na swoim miejscu element, który możemy zignorować w kolejnych turach.

Jednak modyfikujemy nieco funkcję sort, aby zaoszczędzić sobie kroków, gdy stwierdzimy, że jakiś element jest już uporządkowany:

sortowanie funkcji (myArray, value1, value2) {if (value1 == value2) {return myArray; } var temp = mojaTablica [wartość1]; mojaTablica [wartość1] = mojaTablica [wartość2]; mojaTablica [wartość2] = temp; zwróć moją tablicę;}

Aby to osiągnąć dodaliśmy pętlę if, w której sprawdza, czy wartości się zgadzają, czyli czy są już uporządkowane.

3. Sortowanie wstawianiaNa koniec zobaczymy najbardziej wydajny algorytm z tych trzech, ponieważ nie zawsze będziemy potrzebować iteracji N-1, aby umieścić naszą tablicę, jak zobaczymy poniżej.

Ten algorytm wstawiania działa podobnie do umieszczania kart w grze pokerowej, gdy karty są rozdawane.
Zazwyczaj układamy karty według kolorów, a w nich według kolejności rosnącej w następujący sposób:
Najpierw rozdawana jest karta, pojedynczy element, który jest uporządkowany (za unikalność). Następnie, gdy istnieją elementy „j” uporządkowane od najmniejszego do największego, bierzemy element j + 1 i porównujemy go ze wszystkimi elementami, które są już uporządkowane. Jeśli znajdzie mniejszy, ponieważ większe przesunęły się w prawo, ten element (j + 1) jest wstawiany, przesuwając się do reszty.

ten wstaw algorytm przetłumaczone na Język JavaScript następująco:

function insert (myArray) {var tam = mojaTablica.length, temp, place; for (var obj = 0; obj = 0 && mojaTablica [miejsce]> temp; miejsce--) {mojaTablica [miejsce + 1] = mojaTablica [miejsce]; } mojaTablica [miejsce + 1] = temp; } return myArray;}