początkujące algorytmy sortowania w języku JavaScript: Bubble, Selection & Insertion Sort

uporządkowanie wszystkich zbiorów danych w prosty sposób zwiększy czas i zasoby do zarządzania i wyszukiwania. To, czy dane są sortowane, czy nie, bezpośrednio wpłynie na to, jakich metod wyszukiwania możesz użyć i może oznaczać różnicę między wyszukiwaniem wykonującym milion operacji, a 10, jak w przypadku wyszukiwania binarnego.

dla uproszczenia skupimy się tylko na sortowaniu tablicy liczb od najmniejszej do największej, ale te algorytmy można łatwo modyfikować dla innych celów sortowania. Należy pamiętać, że są to bardziej ogólne koncepcje i wzorce, a mniej „instrukcje” do sortowania danych, ponieważ dana implementacja może się znacznie różnić, ale w końcu może koncepcyjnie przypominać te wzorce.

oto praktyczna tablica 50 liczb losowych.

const unsortedArr = ;

będę patrzył na wszystko przez pryzmat Wielkiej notacji O, więc zrozumienie, jak złożoność rośnie w czasie, będzie bardzo pomocne.

Bubble Sort

to jest „Hello World” metod sortowania, nic szalonego, ale robi swoje.

dla każdego elementu w tablicy chcemy sprawdzić, czy następny element jest większy, jeśli jest to swap ich indeksów w tablicy. Aby uniknąć porównywania posortowanych liczb, zaczniemy od tyłu tablicy, podczas gdy inny for loop otrzyma poprzednią liczbę. W ten sposób wszystkie największe wartości gromadzą się, lub „bąbelki w górę”, na końcu.

Animacja Bubble Sort

Grafika/Animacja dzięki VisuAlgo.net

nasza wersja działa odwrotnie niż animacja, ale jest wystarczająco blisko.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

Selection Sort

Selection sort działa jak przeciwieństwo sortowania bąbelkowego, podczas gdy sortowanie bąbelkowe przesuwa wszystkie największe wartości do końca teraz zamierzamy przesunąć minimalne wartości do początku.

przy każdym zapętleniu tablicy wybiera najmniejszą wartość, jeżeli znajdzie niższą wartość, która wtedy stanie się nową najniższą wartością. Gdy pętla zostanie zakończona, zajmie to minimum i umieści ją na przedniej części tablicy przed ponownym uruchomieniem pętli. W ten sposób najniższa wartość każdej iteracji jest układana na początku aż do posortowania całej tablicy.

wybór Sortuj animację

Grafika/Animacja dzięki VisuAlgo.net

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

Insertion Sort

mój osobisty ulubiony i najbardziej wydajny z tych trzech, insertion sort, jest bardziej podobny do tego, jak można sortować coś ręcznie.

patrzymy na tablicę jako dwie części, posortowaną i nieposortowaną, przy czym za każdym razem, gdy znajdziemy nową wartość, wracamy do niej, aby znaleźć jej miejsce w posortowanej połowie. Z każdym dodatkiem nasza posortowana Grupa rośnie, aż stanie się całą tablicą.

Wstawianie Sortuj animację

Grafika/Animacja dzięki VisuAlgo.net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

porównanie

jednym z problemów z użyciem notacji Big O do porównywania algorytmów jest to, że opiera się ona na gorszym scenariuszu, który może być taki sam dla wszystkich algorytmów, dając fałszywe złudzenie, że są równe. Podczas gdy rodzaje bąbelków, selekcji i wstawiania są O(N^2), nie mówi nam to zbyt wiele o średnim lub najlepszym scenariuszu ani o tym, jak różnią się one w zależności od struktury danych.

sortowanie wstawiania wygrywa za każdym razem. Ma również tę zaletę, że nie trzeba mieć całej tablicy przed uruchomieniem,co pozwala sortować rzeczy w czasie rzeczywistym, gdy dane przychodzą.

pamiętaj o tym, ponieważ nie powinieneś decydować, który algorytm jest „najlepszy” przed rozważeniem, jak Twoje dane są już zorganizowane.

podsumowanie

te trzy rozwiązania są dalekie od najlepszych rozwiązań do wydajnego sortowania dużych ilości danych, ale są jednymi z najbardziej intuicyjnych do zanurzenia palców w tym, co może być przytłaczającym oceanem. 🌊