Czym są pętle zagnieżdżone?
Pętle zagnieżdżone to konstrukcja, w której jedna pętla znajduje się wewnątrz drugiej. Oznacza to, że dla każdego obrotu pętli zewnętrznej pętla wewnętrzna może wykonać się wiele razy.
Zastosowanie
Pętle zagnieżdżone są często używane do:
- przetwarzania tablic dwuwymiarowych,
- porównywania elementów tablicy,
- realizacji prostych algorytmów sortowania,
- generowania kombinacji elementów.
W sortowaniu bąbelkowym stosuje się zwykle dwie pętle: zewnętrzna odpowiada za kolejne przebiegi algorytmu, a wewnętrzna porównuje sąsiednie elementy tablicy i wykonuje zamiany.
Przykład
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (tab[j] > tab[j + 1]) {
swap(tab[j], tab[j + 1]);
}
}
}
Ważne na egzaminie
Jeżeli obie pętle mogą wykonać się maksymalnie około n razy, to liczba operacji jest rzędu n * n, czyli złożoność czasowa wynosi O(n²).
Nie oznacza to jednak, że pętle działają na n + 1 elementach. Dla tablicy n-elementowej poprawne indeksy mieszczą się zwykle od 0 do n - 1.