Wprowadzenie do algorytmów sortowania w JavaScript

Podobnie jak w przypadku większości innych języków programowania, możesz napotkać scenariusze, w których musisz posortować niektóre liczby w JavaScript w porządku rosnącym lub malejącym. Aby to zrobić, możemy użyć wielu algorytmów, takich jak sortowanie bąbelkowe, sortowanie selekcyjne, sortowanie scalone, Quicksort itp. Algorytmy te różnią się nie tylko sposobem działania, ale także mają inne wymagania dotyczące pamięci i czasu, zagłęb się w niektóre ważne algorytmy sortowania i zobacz, jak możesz ich użyć w kodzie JavaScript.

Top 6 algorytmów sortowania w JavaScript

Oto niektóre algorytmy sortowania w javascript wyjaśnione poniżej z przykładami:

1. Algorytm sortowania bąbelkowego

Uważane za jedno z najczęstszych narzędzi w tej branży, sortowanie bąbelkowe polega na tworzeniu pętli, która porównuje każdy element w tablicy z innym przedmiotem. Jeśli porównywany przedmiot jest mniejszy niż ten na ręki, zamieniamy się miejscami. Trwa to do momentu, w którym mamy przepustkę, w której żaden element w tablicy nie jest większy niż przedmiot obok.

Sortowanie bąbelkowe ma złożoność czasową O (n 2 ) i złożoność przestrzenną O (n).

Kod:

function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));

Wynik:

2. Algorytm sortowania wyboru

Teraz, gdy już skończyliśmy omawiać algorytm sortowania bąbelkowego, przyjrzyjmy się popularnemu algorytmowi sortowania o nazwie Selekcja sortowania.

W przeciwieństwie do sortowania bąbelkowego, koncentrujemy się na znalezieniu najmniejszej wartości w tablicy, aby wykonać sortowanie. Oto szczegółowy opis działania sortowania selekcyjnego:

  • Zakładamy, że pierwszy element w tablicy jest najmniejszy.
  • Porównujemy ten element do następnego elementu w tablicy.
  • Jeśli następny element jest mniejszy niż ten pod ręką, ustawiamy następny element jako nową najmniejszą wartość.
  • Powtarzamy te kroki, aż dotrzemy do końca tablicy.
  • Kiedy znajdziemy wartość w tablicy mniejszą niż ta, od której zaczęliśmy, zamieniamy ich pozycje.
  • Robimy porównania i przechodzimy do następnego elementu. Aż cała tablica zostanie posortowana.

Podobnie jak algorytm Bubble Sort, sortowanie Selekcja ma złożoność czasową O (n 2 ) i złożoność przestrzenną O (n).

Kod:

function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));

Wynik:

3. Algorytm sortowania korespondencji seryjnej

Podobnie jak sortowanie bąbelkowe i sortowanie selekcyjne, sortowanie korespondencji seryjnej jest jednym z popularnych algorytmów sortowania w informatyce, można go wdrożyć w większości języków programowania i ma dobrą wydajność bez nadmiernego zapotrzebowania na zasoby.

Scal sortowanie używa metody Dziel i rządź, aby posortować tablicę lub dowolną listę elementów. Termin dzieli i pokonuje oznacza, że ​​dzielimy jeden duży problem na kilka mniejszych problemów, a następnie rozwiązujemy te małe problemy. Po rozwiązaniu mniejszych problemów łączymy wyniki, które dają rozwiązanie dużego problemu.

Zrozumienie algorytmu jest proste:

  • Daną tablicę dzielimy na n tablic. Każda z tych tablic zawiera tylko 1 element.
  • Scal tablice, aby utworzyć nową tablicę.
  • Powtarzaj krok 2, aż pozostanie tylko 1 tablica, która będzie tablicą posortowaną.

Kod:

function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));

Wynik:

4. Algorytm szybkiego sortowania

Quicksort jest jednym z najbardziej wydajnych sposobów sortowania elementów w systemach komputerowych. Podobnie do łączenia sortowania, Quicksort działa na algorytmie dzielenia i zdobywania. W tym celu znajdujemy element przestawny w tablicy, aby porównać wszystkie inne tablice elementów, a następnie przesuwamy elementy w taki sposób, że wszystkie przedmioty przed naszymi wybranymi elementami przestawnymi są mniejsze, a wszystkie elementy po elemencie przestawnym są większe. Gdy to zrobimy, kluczem jest powtarzanie tego, a my będziemy mieć uporządkowaną tablicę.

Poniżej przedstawiono kroki, które można wykonać, aby wdrożyć algorytm szybkiego sortowania:

  • Wybieramy element tablicy i nazywamy go „punktem obrotu”
  • Zaczynamy wskaźnik zwany lewym wskaźnikiem, od którego znajduje się pierwszy element w tablicy.
  • Podobnie zaczynamy wskaźnik zwany prawym wskaźnikiem na ostatnim elemencie tablicy.
  • Jeśli wartość elementu na lewym wskaźniku jest mniejsza w porównaniu do wybranego punktu obrotu, przesuwamy lewy wskaźnik na lewo (dodajemy +1) i powtarzamy go, aż wartość lewego wskaźnika będzie większa niż wartość wartość punktu obrotu lub jej równa.
  • Jeśli wartość elementu pod prawym wskaźnikiem na liście jest wyższa niż wartość elementu przestawnego, ustawiamy prawy wskaźnik w lewo. Powtarzaj tę czynność, dopóki wartość po prawej stronie wskaźnika nie będzie niższa niż (lub równa) wartości obrotu.
  • Gdy wartość lewego wskaźnika jest mniejsza lub równa wartości prawego wskaźnika, zamień wartości.
  • Przesuń prawy wskaźnik w lewo o jeden, lewy wskaźnik w prawo o jeden.
  • Powtarzaj, aż lewy i prawy wskaźnik spotkają się.

Kod:

function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);

Wynik:

5. Algorytm sortowania wstawiania

Jeśli chodzi o łatwość implementacji, rodzaj wstawiania jest powszechnie znany jako jeden z prostszych algorytmów. W Sortowaniu wstawiania elementy tablicy są porównywane ze sobą, a następnie ułożone w określonej kolejności. Jest to bardzo podobne do układania kart w talii. Rodzaj wstawiania nazwy pochodzi z procesu wybierania elementu i wstawiania go we właściwe miejsce, a następnie powtarzania go dla wszystkich elementów.

Oto jak działa algorytm:

  • Pierwszy element tablicy jest uważany za już posortowany.
  • Wybierz następny element tablicy.
  • Porównaj wybrany element ze wszystkimi elementami w tablicy.
  • Przesuń każdy element w tablicy, który jest większy niż wartość wybranego elementu.
  • Wstaw element
  • Powtarzaj kroki od 2 do 5, aż tablica zostanie posortowana.

Kod:

function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));

Wynik:

6. Algorytm sortowania sterty

Sortowanie stert to sposób sortowania elementów za pomocą struktury danych „Sterty”. Metoda jest dość podobna do techniki sortowania selekcji, którą omówiliśmy wcześniej. Teraz możesz zastanawiać się nad stertami i jak są one zdefiniowane, zanim przejdziesz do algorytmu, najpierw zrozummy sterty.

W skrócie, sterta jest drzewem binarnym z kilkoma dodanymi regułami. Jedna reguła mówi, że na stosie drzewo musi być kompletnym drzewem binarnym, co oznacza po prostu, że konieczne jest wypełnienie wszystkich węzłów na bieżącym poziomie przed dodaniem kolejnego. Kolejna reguła dla sterty jest taka, że ​​musi istnieć zdefiniowana relacja potomna i nadrzędna z wartościami elementów sterty.

W stertach min wartość rodzica musi być mniejsza niż jego potomków. Jak można się domyślić, w stosie maksimum wartość rodzica musi być większa niż jego potomka.

Teraz, gdy definicje są już na uboczu, rzućmy okiem na działanie heapsortu:

  • Najpierw budujemy maksymalną stertę, która zapewnia, że ​​element o najwyższej wartości znajduje się na górze.
  • Zamieniamy górny element na ostatni element sterty, usuwamy górny element ze sterty i przechowujemy go w posortowanej tablicy.
  • Powtarzamy krok pierwszy i drugi, aż w stosie pozostanie tylko jeden element.

Należy pamiętać, że sterty nie są natywnie obsługiwane w JavaScript, dlatego musimy uciekać się do implementacji stert za pomocą tablic. Złożoność przestrzenna sortowania sterty to O (1), która jest doskonała i chociaż jest nieco bardziej skomplikowana w porównaniu do sortowania scalanego lub sortowania wstawianego, jeśli chodzi o zrozumienie i implementację, myślę, że dla korzyści w zakresie wydajności, ostatecznie lepiej jest użyć w duże projekty.

Kod:

var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);

Wynik:

Wniosek

Sortowanie jest ważną częścią tworzenia aplikacji i stron internetowych z JavaScript. Teraz, gdy znasz już niektóre z najważniejszych algorytmów do wykonania zadania, powinieneś czuć się pewniej w JS Development.

Jednym z ważnych faktów, o których należy pamiętać podczas sortowania, jest to, że tak naprawdę nie trzeba zbytnio stresować się tym, jakiego algorytmu użyć w większości przypadków. Teraz, gdy sprzęt komputerowy jest tak potężny, nowoczesne procesory telefoniczne i stacjonarne nie przejmują się poceniem podczas sortowania nawet setek elementów w ciągu kilku milisekund. Są to tylko przypadki, w których utknąłeś przy wolnym sprzęcie lub sytuacje, w których optymalizujesz każdą sekcję kodu, w których zmiana algorytmów sortowania może być korzystna.

Polecane artykuły

Jest to przewodnik po algorytmach sortowania w JavaScript. Tutaj omawiamy 6 najlepszych algorytmów sortowania w javascript wraz z przykładami i implementacją kodu. Możesz także przejrzeć następujące artykuły, aby dowiedzieć się więcej -

  1. Kompilatory JavaScript
  2. Odwróć w JavaScript
  3. Wprowadzenie do JavaScript
  4. Kwadraty w Javie
  5. Algorytmy szybkiego sortowania w Javie
  6. Tablice w strukturze danych
  7. Algorytm C ++ | Przykłady algorytmu C ++

Kategoria:

Rozwój oprogramowania