R1QX9EB6BE8D1
Zdjęcie przedstawia owoce sezonowe w małych pojemnikach, porzeczki, jagody, borówki, maliny i poziomki.

I_R_W14_M25_Java Szukanie jednoczesne min‑max

Źródło: Alex Block, domena publiczna.

Algorytm jednoczesnego znajdowania minimum i maksimum w wersji optymalnej to świetny przykład na to, jak prosty zabieg logiczny — porównywanie elementów parami — pozwala zaoszczędzić około 25% operacji porównania w stosunku do metody naiwnej.

Poniżej znajdziesz implementację Twojego pseudokodu w języku Java, dostosowaną do standardowego indeksowania tablic od zera.

Implementacja w języku Java

Ponieważ Java nie posiada wbudowanego typu „krotka” (tuple), stworzyłem prostą klasę pomocniczą WynikMinMax, która elegancko przechowuje obie znalezione wartości.

Dlaczego to podejście jest lepsze?

W standardowym (naiwnym) podejściu każdy element porównujemy osobno z minimum i osobno z maksimum. Daje to łącznie 2n porównań.

W Twoim algorytmie:

  • Bierzemy parę elementów.

  • Porównujemy je ze sobą (1 porównanie).

  • Mniejszy porównujemy tylko z aktualnym min (1 porównanie).

  • Większy porównujemy tylko z aktualnym max (1 porównanie).

Razem zużywamy 3 porównania na każde 2 elementy. Matematycznie liczba porównań spada do około 23n, co czyni ten algorytm znacznie bardziej wydajnym przy bardzo dużych zbiorach danych.

Warto zauważyć: W kodzie Java użyłem pętli while zamiast for, aby łatwiej kontrolować „skoki” o dwa elementy oraz obsługę ostatniego, pojedynczego elementu w przypadku tablic o nieparzystej długości.

1
Ćwiczenie 1

Napisz program, wyznaczy jednocześnie minimum i maksimum.

Specyfikacja problemu:

Dane:

  • ciag – ciąg liczb całkowitych zapisany w tablicy; tablica liczb całkowitych

Wynik:

  • min i max – najmniejszy i największy wyraz ciągu; liczba całkowita

RFKL4R537PCMG