Twoje Centrum Szkoleniowe

C++: Sortowanie przez wstawianie (Insertion Sort)

Sortowanie przez wstawianie działa poprzez budowanie posortowanej sekwencji elementów, jeden po drugim. W każdej iteracji, algorytm wybiera jeden z elementów z niesortowanej części zbioru i wstawia go na odpowiednią pozycję w już posortowanej sekcji. Proces ten jest powtarzany, aż wszystkie elementy nie zostaną włączone do posortowanej sekcji. Podobnie jak układasz karty w ręce podczas gry w karty, przenosząc każdą kartę na odpowiednie miejsce w zależności od jej wartości.

 

Cechy charakterystyczne tego algorytmu

Główną cechą sortowania przez wstawianie jest jego prosta implementacja i efektywność w przypadku małych zestawów danych lub gdy dane są już częściowo posortowane. Algorytm ten charakteryzuje się też stabilnością, co oznacza, że zachowuje kolejność równych elementów. Sortowanie przez wstawianie jest algorytmem sortowania 'in-place', co oznacza, że nie wymaga dodatkowej znaczącej ilości pamięci.

 

Porównanie z sortowaniem bąbelkowym, podkreślając różnice

Sortowanie przez wstawianie często jest porównywane z sortowaniem bąbelkowym, ponieważ oba są prostymi algorytmami sortowania. Główna różnica polega na sposobie działania: sortowanie bąbelkowe wielokrotnie przechodzi przez listę, zamieniając sąsiednie elementy będące w niewłaściwej kolejności, podczas gdy sortowanie przez wstawianie tworzy posortowaną sekwencję poprzez wstawianie elementów w odpowiednie miejsce. W efekcie, sortowanie przez wstawianie zwykle okazuje się być bardziej efektywne niż sortowanie bąbelkowe, zwłaszcza gdy lista jest już częściowo posortowana, ponieważ wymaga mniej porównań i zamian.

 

Zasada działania sortowania przez wstawianie

Proces sortowania przez wstawianie polega na podziale zbioru danych na dwie części: posortowaną i niesortowaną. Na początku, pierwszy element zbioru traktujemy jako już posortowany, a resztę jako niesortowaną.

W każdej iteracji algorytm wybiera pierwszy element z niesortowanej części zbioru. Następnie, porównuje go z elementami w posortowanej części, przesuwając każdy z nich o jedno miejsce do przodu, aż znajdzie odpowiednią pozycję dla wybranego elementu. Element ten jest następnie wstawiany na tę pozycję. Proces ten jest powtarzany aż do posortowania wszystkich elementów.

Na każdym etapie algorytmu, posortowana część zbioru danych jest zawsze w porządku. Oznacza to, że w dowolnym momencie, jeśli algorytm zostanie przerwany, posortowana część zbioru będzie uporządkowana. Ta właściwość jest szczególnie przydatna w scenariuszach, gdzie możliwe jest częściowe sortowanie i konieczność szybkiego odnalezienia uporządkowanego podzbioru danych.

 

 

Przykładowa implementacja sortowania przez wstawianie w C++

Napiszmy funkcję, która zaimplementuje sortowanie przez wstawianie. Poniżej przedstawiam przykładowy kod, który pokazuje, jak można tego dokonać:

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // Przesuwaj elementy arr[0..i-1], które są większe od key,
        // o jedną pozycję w prawo
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    std::vector<int> data = {12, 11, 13, 5, 6};
    insertionSort(data);

    std::cout << "Posortowany zbiór: ";
    for(int i = 0; i < data.size(); i++)
        std::cout << data[i] << " ";
    std::cout << std::endl;

    return 0;
}

 

Analiza kodu

1. Inicjalizacja: W funkcji insertionSort, zaczynamy od zdefiniowania rozmiaru wektora arr, który będziemy sortować.

2. Iterowanie przez elementy: Następnie, używamy pętli for do iterowania przez elementy wektora, zaczynając od drugiego elementu (indeks 1), ponieważ pierwszy element jest już w sposób naturalny 'posortowany'.

3. Wybieranie klucza: W każdej iteracji wybieramy key, czyli element do posortowania, a następnie porównujemy go z elementami leżącymi przed nim.

4. Wstawianie elementu: Używamy pętli while do przesuwania elementów większych od key o jedną pozycję w prawo, aż znajdziemy odpowiednie miejsce dla key. Następnie wstawiamy key na tę pozycję.

5. Wyświetlanie posortowanego zbioru: W funkcji main, po wywołaniu insertionSort, posortowany zbiór jest wypisywany na ekran.

Znaczenie i rola poszczególnych instrukcji i zmiennych

• Zmienna n przechowuje rozmiar wektora, co jest niezbędne do kontroli granic pętli.
• Zmienna key jest elementem, który jest aktualnie sortowany i wstawiany na odpowiednie miejsce.
• Zmienna j służy do iterowania przez posortowaną już część wektora i znajdowania odpowiedniego miejsca dla key.

 

 

Analiza złożoności sortowania przez wstawianie

 

Złożoność czasowa algorytmu

Złożoność czasowa sortowania przez wstawianie zależy od początkowego uporządkowania danych. W najlepszym przypadku, gdy dane są już posortowane, algorytm wykonuje tylko jedno porównanie na element, co daje złożoność czasową O(n). W najgorszym przypadku, gdy dane są posortowane w odwrotnej kolejności, każdy nowy element musi być porównywany z wszystkimi wcześniejszymi elementami, co daje złożoność czasową O(n²). Średnio można oczekiwać złożoności czasowej pomiędzy tymi dwoma skrajnościami, w zależności od stopnia nieuporządkowania danych.

 

Złożoność przestrzenna algorytmu

Sortowanie przez wstawianie jest algorytmem sortowania 'in-place', co oznacza, że nie wymaga dodatkowej znaczącej ilości pamięci poza przekazywanym zbiorze danych. Jego złożoność przestrzenna wynosi O(1), ponieważ używa tylko stałej ilości dodatkowej pamięci dla swoich operacji.

 

 

Praktyczne zastosowania i ograniczenia sortowania przez wstawianie

 

Przykłady sytuacji, w których sortowanie przez wstawianie jest efektywne

1. Małe zbiory danych: Sortowanie przez wstawianie jest szczególnie efektywne, gdy mamy do czynienia z małymi zbiorami danych. Jego prostota i minimalne wymagania pamięciowe sprawiają, że jest szybszy niż bardziej skomplikowane algorytmy dla niewielkiej liczby elementów.

2. Częściowo posortowane dane: Ten algorytm jest również efektywny, gdy dane wejściowe są już częściowo posortowane. W takich przypadkach liczba porównań i przesunięć jest znacznie mniejsza, co skutkuje szybszym wykonaniem.

3. Sortowanie online: Ze względu na swoje właściwości, sortowanie przez wstawianie jest odpowiednie do zastosowań 'online', gdzie dane są sortowane w miarę ich otrzymywania. Jest to przydatne w sytuacjach, gdzie dane napływają stopniowo, a ich szybkie sortowanie jest wymagane.

4. Niewielkie użycie pamięci: Jako algorytm sortowania 'in-place', sortowanie przez wstawianie nie wymaga dodatkowej pamięci, co czyni go idealnym wyborem dla systemów z ograniczonymi zasobami.

 

Dyskusja na temat ograniczeń algorytmu

1. Niska wydajność dla dużych zbiorów danych: Głównym ograniczeniem sortowania przez wstawianie jest jego niska wydajność w przypadku dużych zbiorów danych. Złożoność czasowa O(n²) sprawia, że algorytm staje się niewydajny w porównaniu do szybszych algorytmów, takich jak quicksort czy mergesort.

2. Wrażliwość na początkowy porządek danych: Chociaż sortowanie przez wstawianie jest efektywne dla częściowo posortowanych danych, jego wydajność znacznie spada, gdy dane są posortowane w odwrotnej kolejności.

3. Ograniczona skalowalność: Z powodu swojej złożoności czasowej, sortowanie przez wstawianie nie skaluje się dobrze, co oznacza, że jego użycie jest ograniczone do specyficznych, mniejszych zastosowań.