Spis treści[Ukryć][Pokazać]
Informatyka polega na zrozumieniu złożoności algorytmów i struktur danych.
Masz listę elementów, które należy posortować, ale nie masz czasu ani zasobów, aby użyć bardziej złożonego algorytmu sortowania.
Sortowanie przez wstawianie jest jednym z najprostszych algorytmów sortowania, ale może być powolne w przypadku dużych list.
Łatwa implementacja i zrozumienie sprawiły, że ta metoda stała się ulubioną wśród programistów. Jest idealny do małych list lub gdy potrzebujesz szybkiego rozwiązania.
W tym poście na blogu przyjrzymy się złożoności czasowej sortowania wstawiania. Ten algorytm jest używany do sortowania tablic i ma czas wykonania O(n2). Oznacza to, że złożoność czasowa wzrasta wraz z rozmiarem tablicy.
Jednak ten algorytm może być często szybszy niż inne algorytmy sortowania, takie jak quicksort.
Przyjrzyjmy się bliżej, jak działa sortowanie przez wstawianie!
Co to jest algorytm sortowania przez wstawianie?
Jeden element na raz, sortowanie przez wstawianie generuje tablicę, którą można sortować, często nazywaną listą.
Na przykład sortowanie jest stosowane w skomplikowanych programach komputerowych, takich jak kompilatory, gdzie kolejność tokenów jest istotna dla interpretacji programu.
Jak działa sortowanie przez wstawianie?
Kiedy używamy sortowania przez wstawianie do sortowania tablicy, algorytm zaczyna od znalezienia najmniejszego elementu na liście i wstawienia go we właściwej pozycji.
Następnie znajduje następny najmniejszy element i umieszcza go we właściwej pozycji i tak dalej.
Algorytm działa poprzez przeglądanie listy, porównując każdy element z poprzednim.
Jeśli elementy są w złej kolejności, algorytm je zamienia. Następnie sprawdza, czy lista jest posortowana, a jeśli tak, algorytm się kończy.
W praktyce sortowanie przez wstawianie jest często implementowane przy użyciu kilku linijek kodu, co czyni go popularnym wyborem do sortowania małych tablic. Jednak przy korzystaniu z tego algorytmu należy wziąć pod uwagę złożoność czasową.
Przykład:
Oto przykład działania sortowania przez wstawianie. Użyjemy następującej tablicy:
1, 2, 3, 4, 5, 6
Algorytm zaczyna od znalezienia najmniejszej pozycji na liście, czyli 1. Następnie umieszcza ją we właściwej pozycji, pierwszej pozycji. Następnie znajduje następny najmniejszy element, czyli 2. Wstawia go we właściwą pozycję, czyli drugą pozycję.
Następnie znajduje następny najmniejszy element, czyli 3. Wstawia go we właściwą pozycję, czyli trzecią pozycję.
Następnie znajduje następny najmniejszy element, czyli 4. Wstawia go we właściwą pozycję, czyli na czwartą pozycję, i tak dalej. Lista jest teraz posortowana!
Na przykładzie widać, że algorytm dokonuje sześciu porównań i zamiany, aby posortować listę. To dlatego, że zajmuje n2 porównania i zamiany, aby posortować listę n pozycji. W tym przypadku n=6.
Jak poprawić złożoność czasu sortowania wstawiania?
Podczas sortowania przez wstawianie ma czas wykonania O(n2), można go ulepszyć, używając lepszego algorytmu sortowania, takiego jak quicksort.
Quicksort ma środowisko wykonawcze O(n log n), które jest znacznie szybsze niż O(n2).
Jednak w niektórych przypadkach sortowanie przez wstawianie może być szybsze niż sortowanie szybkie.
Na przykład, jeśli lista jest już uporządkowana, sortowanie przez wstawianie zajmie mniej czasu niż sortowanie szybkie.
W praktyce sortowanie przez wstawianie jest często implementowane przy użyciu kilku linijek kodu, co czyni go popularnym wyborem do sortowania małych tablic.
Jednak przy korzystaniu z tego algorytmu należy wziąć pod uwagę złożoność czasową.
Złożoność czasowa
Złożoność najgorszego przypadku O(n2):
Złożoność czasowa wzrasta wraz z rozmiarem tablicy. to trwa n2 porównania i zamiany, aby posortować listę n pozycji.
Na przykład, jeśli mamy tablicę o rozmiarze 1000, algorytm wykona 1,000,000 XNUMX XNUMX porównań i zamiany, aby posortować tablicę.
Złożoność najlepszego przypadku O(n):
Złożoność czasowa jest taka sama jak wielkość tablicy wejściowej. i
t zajmuje n porównań i zamian, aby posortować listę n pozycji. Rozważmy na przykład tablicę o rozmiarze 5. Algorytm wykona pięć porównań i zamiany, aby posortować tablicę.
Średnia złożoność przypadku O(n2):
W tym przypadku złożoność czasowa mieści się między złożonością najgorszego i najlepszego przypadku.
to trwa n2 porównania i zamiany, aby posortować listę n pozycji.
W ten sposób sortowanie przez wstawianie jest stabilnym algorytmem sortowania.
Dlaczego sortowanie wstawiania jest stabilne?
Sortowanie przez wstawianie jest stabilne, ponieważ zachowuje kolejność równych elementów w tablicy wejściowej.
Jest to ważne w przypadku wielu aplikacji, takich jak wyszukiwanie danych lub analiza finansowa. Na przykład, jeśli mamy dwie listy liczb i chcemy je porównać, musimy upewnić się, że zachowana jest kolejność elementów.
Jeśli listy nie będą posortowane, nie będziemy ich dokładnie porównywać.
Dodaj komentarz