Streszczenie Sortowanie przez wstawianie (insertion sort)

Sortowanie przez wstawianie (insertion sort) – Kompleksowy Przewodnik

Streszczenie Test wiedzy Fiszki Podcast Mapa myśli

Sortowanie przez wstawianie: Porządkowanie Danych Krok po Kroku

Sortowanie przez wstawianie (ang. insertion sort) to jeden z najbardziej intuicyjnych algorytmów sortowania, służący do uporządkowania elementów w zbiorze (na przykład w tablicy) w określonej kolejności – rosnącej lub malejącej. Jest to algorytm porównawczy, co oznacza, że jego działanie opiera się na porównywaniu par elementów.

Choć sortowanie przez wstawianie jest algorytmem stosunkowo prostym, stanowi fundamentalny element w nauce algorytmów sortowania. Jest również praktycznie wykorzystywany w specyficznych sytuacjach, takich jak sortowanie niewielkich zbiorów danych lub jako składowa bardziej złożonych algorytmów (na przykład introsort).

Zasada działania – Analogia z sortowaniem kart w ręku

Najłatwiej zrozumieć sortowanie przez wstawianie, wyobrażając sobie codzienną czynność: sortowanie kart w ręku. Pomyśl o tym w ten sposób:

Masz w jednej ręce już posortowane karty, a w drugiej stos kart, które dopiero czekają na uporządkowanie. Kolejno bierzesz po jednej karcie ze stosu i wstawiasz ją w odpowiednie miejsce wśród tych już posortowanych. Jeśli jest to konieczne, przesuwasz inne karty, aby zrobić miejsce dla nowej. Powtarzasz ten proces, aż wszystkie karty zostaną wstawione i posortowane.

Formalnie, algorytm dzieli tablicę na dwie części:

Część posortowana: Zawiera elementy, które są już w odpowiedniej kolejności.
Część nieposortowana: Zawiera elementy, które dopiero czekają na posortowanie.

Początkowo, część posortowana zawiera tylko pierwszy element tablicy (ponieważ pojedynczy element jest zawsze posortowany). Reszta tablicy stanowi część nieposortowaną. W każdej iteracji algorytm pobiera pierwszy element z części nieposortowanej (nazywany „kluczem”) i wstawia go w odpowiednie miejsce w części posortowanej. Aby to zrobić, porównuje klucz z elementami w części posortowanej, przesuwając większe elementy o jedną pozycję w prawo, aż znajdzie właściwe miejsce dla klucza.

Klucz (Key): Element z nieposortowanej części tablicy, który jest aktualnie wstawiany do części posortowanej.

Algorytm (pseudokod)

Poniżej przedstawiono pseudokod algorytmu sortowania przez wstawianie dla tablicy $A$ o długości $n$ (indeksowanej od $0$ do $n-1$):

PROCEDURA SortowaniePrzezWstawianie(A, n):
    DLA i OD 1 DO n-1:
        klucz = A[i]
        j = i - 1
        DOPÓKI j >= 0 ORAZ A[j] > klucz:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = klucz
KONIEC PROCEDURY

Wyjaśnienie pseudokodu:

Pętla zewnętrzna DLA i OD 1 DO n-1: Ta pętla iteruje przez każdy element tablicy, począwszy od drugiego elementu (o indeksie $1$), aż do ostatniego. Każdy element $A[i]$ jest traktowany jako „klucz”, który ma zostać wstawiony do już posortowanej części tablicy $A[0 \ldots i-1]$. Pierwszy element $A[0]$ jest uznawany za już posortowany.
klucz = A[i]: Bieżący element z nieposortowanej części jest przechowywany w zmiennej klucz. Jest to element, który będziemy wstawiać.
j = i - 1: Zmienna j wskazuje na ostatni element w aktualnie posortowanej części tablicy.
Pętla wewnętrzna DOPÓKI j >= 0 ORAZ A[j] > klucz: Ta pętla przesuwa elementy w posortowanej części tablicy. Porównuje klucz z elementami $A[j]$ (idąc od prawej do lewej w posortowanej części). Jeśli $A[j]$ jest większe od klucza, oznacza to, że $A[j]$ musi zostać przesunięte w prawo, aby zrobić miejsce dla klucza.
A[j + 1] = A[j]: Element $A[j]$ jest przesuwany o jedną pozycję w prawo.
j = j - 1: Wskaźnik j jest zmniejszany, aby przejść do poprzedniego elementu w posortowanej części.
A[j + 1] = klucz: Gdy pętla wewnętrzna się zakończy (czyli znajdziemy element mniejszy lub równy kluczowi, albo dojdziemy do początku tablicy), oznacza to, że znaleźliśmy właściwe miejsce dla klucza. klucz jest wstawiany na pozycję $j + 1$.

Przykład działania krok po kro

Zarejestruj się po pełne podsumowanie

FiszkiTest wiedzyStreszczeniePodcastMapa myśli

Zacznij za darmo

Masz już konto? Zaloguj się

Sortowanie przez Wstawianie

Klíčová slova: Sortowanie przez wstawianie, Złożoność algorytmu

Klíčové pojmy: Sortowanie przez wstawianie (insertion sort) to algorytm porównawczy służący do porządkowania elementów w tablicy., Działa na zasadzie dzielenia tablicy na część posortowaną i nieposortowaną., W każdej iteracji pobiera 'klucz' z części nieposortowanej i wstawia go w odpowiednie miejsce w części posortowanej., Przesuwanie elementów w części posortowanej odbywa się, aby zrobić miejsce dla wstawianego 'klucza'., Pętla zewnętrzna (`DLA i OD 1 DO n-1`) iteruje przez każdy element do wstawienia., Pętla wewnętrzna (`DOPÓKI j >= 0 ORAZ A[j] > klucz`) odpowiada za znajdowanie miejsca i przesuwanie elementów., Algorytm jest stabilny, co oznacza zachowanie względnej kolejności równych elementów., Jest efektywny dla małych zbiorów danych i tablic prawie posortowanych., Jest to algorytm sortujący 'w miejscu' (in-place), zużywający minimalną dodatkową pamięć $O(1)$., Może działać jako algorytm 'online', sortując dane w miarę ich napływania., Najłatwiej zrozumieć jego działanie na analogii z sortowaniem kart w ręku.

## Sortowanie przez wstawianie: Porządkowanie Danych Krok po Kroku Sortowanie przez wstawianie (ang. **insertion sort**) to jeden z najbardziej intuicyjnych algorytmów sortowania, służący do uporządkowania elementów w zbiorze (na przykład w tablicy) w określonej kolejności – rosnącej lub malejącej. Jest to **algorytm porównawczy**, co oznacza, że jego działanie opiera się na porównywaniu par elementów. Choć sortowanie przez wstawianie jest algorytmem stosunkowo prostym, stanowi **fundamentalny element** w nauce algorytmów sortowania. Jest również praktycznie wykorzystywany w specyficznych sytuacjach, takich jak sortowanie niewielkich zbiorów danych lub jako składowa bardziej złożonych algorytmów (na przykład introsort). ### Zasada działania – Analogia z sortowaniem kart w ręku Najłatwiej zrozumieć sortowanie przez wstawianie, wyobrażając sobie codzienną czynność: **sortowanie kart w ręku**. Pomyśl o tym w ten sposób: Masz w jednej ręce już posortowane karty, a w drugiej stos kart, które dopiero czekają na uporządkowanie. Kolejno bierzesz po jednej karcie ze stosu i wstawiasz ją w odpowiednie miejsce wśród tych już posortowanych. Jeśli jest to konieczne, przesuwasz inne karty, aby zrobić miejsce dla nowej. Powtarzasz ten proces, aż wszystkie karty zostaną wstawione i posortowane. Formalnie, algorytm dzieli tablicę na dwie części: 1. **Część posortowana:** Zawiera elementy, które są już w odpowiedniej kolejności. 2. **Część nieposortowana:** Zawiera elementy, które dopiero czekają na posortowanie. Początkowo, część posortowana zawiera tylko **pierwszy element tablicy** (ponieważ pojedynczy element jest zawsze posortowany). Reszta tablicy stanowi część nieposortowaną. W każdej iteracji algorytm pobiera pierwszy element z części nieposortowanej (nazywany „**kluczem**”) i wstawia go w odpowiednie miejsce w części posortowanej. Aby to zrobić, porównuje klucz z elementami w części posortowanej, przesuwając większe elementy o jedną pozycję w prawo, aż znajdzie właściwe miejsce dla klucza. > **Klucz (Key):** Element z nieposortowanej części tablicy, który jest aktualnie wstawiany do części posortowanej. ### Algorytm (pseudokod) Poniżej przedstawiono pseudokod algorytmu sortowania przez wstawianie dla tablicy $A$ o długości $n$ (indeksowanej od $0$ do $n-1$): ``` PROCEDURA SortowaniePrzezWstawianie(A, n): DLA i OD 1 DO n-1: klucz = A[i] j = i - 1 DOPÓKI j >= 0 ORAZ A[j] > klucz: A[j + 1] = A[j] j = j - 1 A[j + 1] = klucz KONIEC PROCEDURY ``` **Wyjaśnienie pseudokodu:** 1. **Pętla zewnętrzna `DLA i OD 1 DO n-1`**: Ta pętla iteruje przez każdy element tablicy, począwszy od drugiego elementu (o indeksie $1$), aż do ostatniego. Każdy element $A[i]$ jest traktowany jako „klucz”, który ma zostać wstawiony do już posortowanej części tablicy $A[0 \ldots i-1]$. Pierwszy element $A[0]$ jest uznawany za już posortowany. 2. **`klucz = A[i]`**: Bieżący element z nieposortowanej części jest przechowywany w zmiennej `klucz`. Jest to element, który będziemy wstawiać. 3. **`j = i - 1`**: Zmienna `j` wskazuje na ostatni element w aktualnie posortowanej części tablicy. 4. **Pętla wewnętrzna `DOPÓKI j >= 0 ORAZ A[j] > klucz`**: Ta pętla przesuwa elementy w posortowanej części tablicy. Porównuje `klucz` z elementami $A[j]$ (idąc od prawej do lewej w posortowanej części). Jeśli $A[j]$ jest większe od `klucza`, oznacza to, że $A[j]$ musi zostać przesunięte w prawo, aby zrobić miejsce dla `klucza`. 5. **`A[j + 1] = A[j]`**: Element $A[j]$ jest przesuwany o jedną pozycję w prawo. 6. **`j = j - 1`**: Wskaźnik `j` jest zmniejszany, aby przejść do poprzedniego elementu w posortowanej części. 7. **`A[j + 1] = klucz`**: Gdy pętla wewnętrzna się zakończy (czyli znajdziemy element mniejszy lub równy `kluczowi`, albo dojdziemy do początku tablicy), oznacza to, że znaleźliśmy właściwe miejsce dla `klucza`. `klucz` jest wstawiany na pozycję $j + 1$. ### Przykład działania krok po kro