Wprowadzenie do sortowania wstawianego w JavaScript
Sortowanie jest jedną z ważnych koncepcji, których programiści uczą się, aby rozpocząć swoją przygodę z informatyką, niezależnie od wybranego języka programowania. Sortowanie pomaga nam zlokalizować dane docelowe, które chcemy wyszukać w szybszy i wygodny sposób, sortując je w kolejności rosnącej lub malejącej.
Algorytmy sortowania służą do zmiany kolejności elementów, w których elementem może być liczba lub ciąg znaków. Istnieje wiele rodzajów algorytmów sortowania opartych na ich metodzie sortowania i podejściu stosowanym do sortowania elementów, a każdy typ ma swoje zalety i wady.
Na tym blogu skupimy się na rodzaju wstawiania, typowym, łatwym do zrozumienia i wdrożenia.
Co to jest Sortowanie według wstawiania w JavaScript?
Sortowanie wstawiania jest prostym, łatwym do zrozumienia algorytmem, który najlepiej działa z małą listą danych, sortując każdy element na liście danych jeden po drugim od lewej do prawej. Jest również znany jako sortowanie porównawcze, w którym porównuje bieżącą wartość z innymi wartościami na tej samej sortowanej liście danych. Stosuje iteracyjne podejście do umieszczania każdego elementu we właściwej kolejności na liście danych.
Im więcej czasu zajmuje sortowanie algorytmu, tym bardziej mówi się, że jego wydajność jest zła i należy rozważyć inny algorytm do sortowania danych. Sortowanie wstawiania ma złożoność czasową O (n²) lub przebiega kwadratowo w celu posortowania listy danych w najgorszym przypadku. Zwykle nie jest to bardzo skuteczne i nie powinno się go stosować w przypadku dużych list. Jednak zwykle przewyższa zaawansowane algorytmy, takie jak szybkie sortowanie lub scalanie na mniejszych listach.
Sortowanie przez wstawianie, przez większość czasu jest bardziej wydajne niż inne algorytmy sortowania kwadratowego, takie jak sortowanie bąbelkowe lub sortowanie selekcyjne. Najlepszym scenariuszem jest czas O (n) lub liniowy, który występuje, jeśli tablica wejściowa jest już posortowana. Średnio czas działania sortowania przez wstawianie jest nadal kwadratowy.
W poniższym przykładzie będziemy mieli proste podejście na wysokim poziomie do sortowania danych przechowywanych w strukturze danych tablicowych i użyj jego metody sortowania do sortowania danych bez implementacji żadnych algorytmów.
Przykład - algorytm sortowania wstawiania
Kod:
// Declaring unsorted data and storing it in array data structure
var dataArray = (96, 5, 42, 1, 6, 37, 21) // Function - Insertion Sort Algo.
function insertSort(unsortedData) (
for (let i = 1; i < unsortedData.length; i++) (
let current = unsortedData(i);
let j;
for(j=i-1; j >= 0 && unsortedData(j) > current;j--) (
unsortedData(j + 1) = unsortedData(j) )
unsortedData(j + 1) = current;
)
return unsortedData;
)
// print sorted array
console.log(insertSort(dataArray));
Wynik:
Objaśnienie: W algorytmie zaimplementowaliśmy 2 pętle for, zewnętrzna pętla for służy do iteracji elementów tablicy, a wewnętrzna pętla for służy do sortowania elementów tablicy w porządku rosnącym według ich wartości. Bieżąca zmienna przechowuje bieżącą wartość tablicy, a zmienna j jest ustawiona na jedną wartość mniejszą niż bieżąca pozycja indeksu tablicy. Sprawdzamy, czy bieżący element (bieżący) jest mniejszy niż wartość tablicy w pozycji j (unsortedData (j) ), a jeśli to prawda, sortujemy te wartości.
Iteracja 1 - bieżąca (96): (96, 5, 42, 1, 6, 37, 21)
Iteracja 2 - bieżąca (5): (5, 96, 42, 1, 6, 37, 21)
Iteracja 3 - prąd (42): (5, 42, 96, 1, 6, 37, 21)
Iteracja 4 - prąd (1): (1, 5, 42, 96, 6, 37, 21)
Iteracja 5 - prąd (6): (1, 5, 6, 42, 96, 37, 21)
Iteracja 6 - prąd (37): (1, 5, 6, 37, 42, 96, 21)
Iteracja 7 - prąd (21): (1, 5, 6, 21, 37, 42, 96)
Iteracja zewnętrzna pętli rozpoczyna się od 1. pozycji indeksu, ponieważ chcemy przesunąć najmniejszy element na lewą stronę, dlatego porównujemy, czy bieżący element jest mniejszy niż elementy po jego lewej stronie.
Rodzaje sortowania
Typy algorytmów używanych do sortowania danych obejmują następujące koncepcje lub pomysły w ich podejściu do sortowania danych:
- Porównanie a strategie nieporównywalne,
- Implementacja iteracyjna kontra rekurencyjna,
- Paradygmat „dziel i rządź” (to czy tamto),
- Podejście losowe.
Rozważmy kilka przykładów:
1. Scal sortowanie wykorzystuje podejście dziel i zwyciężaj, aby posortować elementy w tablicy.
2. Sortowanie wstawiane, sortowanie bąbelkowe jest sortowaniem opartym na porównaniu.
Po posortowaniu danych łatwiej jest znaleźć optymalne rozwiązanie złożonych problemów. na przykład,
- Poszukiwanie określonej wartości,
- Znalezienie minimalnej lub maksymalnej wartości,
- Testowanie niepowtarzalności i usuwanie duplikatów,
- Liczenie, ile razy pojawiła się określona wartość itp.
Wniosek
W tym artykule omówiliśmy definicję rodzaju wstawiania i jego złożoność czasową oraz różne inne typy algorytmów sortowania w oparciu o ich podejście. Badanie różnych algorytmów sortowania pomaga nam określić, który z nich jest bardziej odpowiedni w określonych okolicznościach lub użyć przypadków, które pomagają nam szybciej sortować dane.
Polecane artykuły
Jest to przewodnik po sortowaniu wstawianym w JavaScript. Tutaj omawiamy na przykład, czym jest sortowanie wstawiane w javascript i jego typy. Możesz także przejrzeć następujące artykuły, aby dowiedzieć się więcej -
- Wzory w JavaScript
- Instrukcja Case w JavaScript
- Instrukcje warunkowe w JavaScript
- Obiekty JavaScript
- Różne rodzaje pętli z jej zaletami