Jednoczesne wyszukiwanie min i max

powrót

Algorytm, który wyszukuje minimum i maksimum w optymalny sposób znajduje się w tym miejscu. Omawiany algorytm będzie oparty na zasadzie klasycznego wyszukiwania tych elementów i jest opisany tutaj.

Zastosowany algorytm wykonuje $$2\cdot n-2$$ porównań elementów zbioru.

Prześledźmy ciąg:

$$4,\ 6,\ 3,\ 1,\ 8,\ 4$$

 Postępujemy według schematu:

• do zmiennych MIN i MAX przypisujemy pierwszą liczbę: MIN = MAX = 4
• następny element zbioru sprawdzamy, czy jest większy niż MAX (if(6 > 4))
• jeśli tak, to zmienną MAX nadpisujemy tą wartością (MAX = 6)
• teraz sprawdzamy, czy ten element jest mniejszy od MIN (if(6 < 4))
• jeśli tak, to zmienną MIN zastępujemy tą wartością (w tym przypadku warunek nie jest spełniony)
• czynność tą postarzymy do wyczerpania liczb w zbiorze

Ostatecznie otrzymujemy:

• MIN = 1
• MAX = 8

Rozwiązanie w C++:

//algorytm.edu.pl
#include<iostream>
using namespace std;

int main()
{
	int tab[] = {1, 3, 4, 5, 2, 0, 6, 9, 8}, MIN, MAX;
	
	MIN = MAX = tab[0];
	
	for(int i=1; i < 9; i++)
	{
		if(tab[i] > MAX)
			MAX = tab[i];
			
		if(tab[i] < MIN)
			MIN = tab[i];
	}
	
	cout<<"MAX: "<<MAX<<"\nMIN: "<<MIN<<endl;

	return 0;
}

Out: 

• MAX: 9
• MIN: 0