Ten artykuł jest częścią serii dotyczącej algorytmów sortowania w języku JavaScript. Resztę serii znajdziecie tutaj. Jeśli nie znasz algorytmów sortowania lub ogólnie algorytmów, przeczytaj najpierw ten artykuł, aby uzyskać solidne podstawy do dalszego działania. Dzisiaj omówię tajniki wstawiania. Sortowanie wstawiania jest bardziej złożone, ale trochę bardziej użyteczne niż sortowanie bąbelkowe. Najgorszy scenariusz jest podobny do Bubble sort, ale jego najlepszy przypadek sprawia, że nadaje się do czasów, gdy jesteś całkiem pewien, że lista prawie posortowana lub prawdopodobnie już posortowana. Spójrzmy na to z szerszej perspektywy.
sortowanie wstawiania działa poprzez sprawdzenie każdego elementu w liście (zaczynając od drugiego elementu) i porównanie go z poprzednim elementem. Jeśli element przed jest większy, są one zamieniane. Trwa to do momentu, gdy element będzie mniejszy, wtedy zrobimy to samo dla następnego elementu na liście.
sortowanie wstawiania nie jest takie złe.. pod warunkiem, że użyjesz go w odpowiednich okolicznościach.
- jest szybszy niż większość algorytmów sortowania O(N log N) dla małych list.
- jest niezwykle wydajny w zakresie pamięci, wymagając jedynie o(1) dodatkowego miejsca na pojedynczy element, który jest przenoszony.
- jest stabilny — równe elementy pojawiają się w tej samej kolejności na posortowanej liście.
- jest adaptacyjny — jest szybki podczas sortowania najczęściej posortowanych list lub podczas dodawania elementów do już posortowanej listy.
- to bardzo łatwe do wdrożenia!
złożoność
złożoność czasowa tego algorytmu, w najgorszym przypadku, jest kwadratowa — O(n2). Gdy n dąży do nieskończoności, średni przypadek zbliża się do najgorszego przypadku podzielonego przez dwa. Ponieważ jednak lista jest posortowana lub prawie tak, może być O (n) w najlepszym przypadku, a zatem dobrze dostosowana do tego scenariusza.
gdy jest szybki
jak wspomniano powyżej, może być szybki w pewnych okolicznościach. Rozważmy tablicę, przy użyciu algorytmu takiego jak merge sort nadal będziemy musieli rozdzielić wszystkie elementy, a następnie scalić je z powrotem. Z insertion sort musimy tylko sprawdzić, czy są w poprawnej kolejności 'posortowane do tej pory’, a następnie przesuwamy je wszystkie w górę o jeden indeks dla 1.
ponieważ sortowanie wstawiania jest sortowaniem adaptacyjnym, czyni go również „algorytmem online”, co oznacza, że możemy rozpocząć sortowanie przed otrzymaniem wszystkich elementów, a następnie scalić listy po zakończeniu sortowania częściowego.
Pseudokod
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
Kod
następny? Połącz sortowanie. Jeden z najczęściej używanych algorytmów sortowania w przeglądarkach.
