[c++] l’algoritmo del massimo e minimo simultanei

[banino84]

Ragazzi qualcuno mi saprebbe spiegare questo algoritmo e mi potrebbe dire come implementarlo in c++ con la tecnica del divide et impera?
grazie

[oregon]

http://www.di.unito.it/~deligu/didat...deEtImpera.pdf

[banino84]

Mi sono implementato l'algoritmo del mergesort. L'algoritmo dei minimi e massimi simultanei dovrebbe fare questo:
1. SE LA DIMENSIONE DEL VETTORE NON SUPERA 2,ALLORA CALCOLA DIRETTAMENTE, MEDIANTE UNUNICO CONFRONTO, IL MINIMO E IL MASSIMO

2. ALTRIMENTI, DIVIDI IL VETTORE IN DUESOTTOVETTORI DELLA STESSA DIMENSIONE,CALCOLA RICORSIVAMENTE IL MINIMO MIN1E ILMASSIMO MAX1DEL PRIMO SOTTOVETTORE PRIMO SOTTOVETTORE E ILMINIMO MIN2E MAX2DEL SECONDO SECONDOSOTTOVETTORE SOTTOVETTORE

3. DETERMINA IL MINIMO E IL MASSIMO DEL VETTORE VETTORECOMPLESSIVO CONFRONTANDO MIN1 CON MIN2 E COMPLESSIVO CONFRONTANDO MIN1 CON MIN2 EMAX1 CON MAX2 MAX1 CON MAX2

come potrei modificare il codice sottostante per avere un algoritmo per il i min e massimi simultanei?

/**
Metodo MergeSort
*/




#include <string>
#define MAX 10
using namespace std;
typedef int start;
typedef int end;
typedef int Item;




/*
* Ricomponi i risultati ottenuti al passo precedente ed ottieni la soluzione complessiva
* (impera)
*/




void impera(Item a[], start left, int center, end right) {
	Item* aux = new int[right + 1];
	int i,j;
	for (i = center+1; i > left; i--)
		aux[i-1] = a[i-1];
		
	for (j = center; j < right; j++) 
		aux[right+center-j] = a[j+1];
		
	for (int k = left; k <= right; k++)
		if (aux[j] < aux[i]) 
			a[k] = aux[j--];
		else
			a[k] = aux[i++];
        delete [] aux;
}




/*
* Dividi il vettore in due sottovettori di dimensione inferiore all'originale ed
* esegui l'algoritmo ricorsivamente sui due sottovettori (divide)
*/


void divide(Item a[], start inizio,end fine) {
    
	if (inizio<fine) {
		int media = (inizio+fine)/2;
		divide(a, inizio, media);
		divide(a, media+1, fine);
		impera(a, inizio, media, fine);
        }
        
}