Informatica 2 Liceo Scientifico Scienze Applicate/esercizi3 funzioni

Quicksort

Programma che implementa il Quicksort tramite l'uso di un array di puntatori a funzione. Sono preferibili passaggi reference piuttosto che per valore perché non sono create copie dei dati in memoria (risparmio di tanto spazio e tempo per valori molto grandi).

Notare che nello spazio dei nomi standard è già definita una funzione sort() e una stable_sort(). La prima usa una versione del Quicksort, la seconda Mergesort. Perciò non serve crearsi ogni volta un proprio algoritmo di ordinamento visto che lo spazio dei nomi standard mette già a disposizione algoritmi di sorting. È addirittura possibile passare una funzione come parametro che imposta l’ordinamento, come qui sotto.

 
#include <iostream>
using std::cout;
using std::cin;
#include <iomanip>
using std::setw;
//Per il tipo "size_t" (unsigned long long) 
#include <cstdlib>

//Prototipi delle funzioni
void quickSort(int [], const size_t &, bool (*)(const int &, const int &));
void partition(int [], const size_t, const size_t &, bool (*)(const int &, const int &));
inline void swap(int &, int &);

//Funzioni per l'ordinamento
bool crescente(const int &a, const int &b) { return a>b; }
bool decrescente(const int &a, const int &b) { return a<b; }

int main()
{
	
	//Array da ordinare e la sua dimensione
	int num[] = {5, 1, 3, 9, 0, 6, 4, 2, 7};
	const size_t dimensione = sizeof(num)/sizeof(int);
	
	//Array di puntatori a funzione per la scelta
	bool (*compara[])(const int &, const int &) = {crescente, decrescente};
	int scelta;
	
	//Ordinamento in base alla scelta
	cin >> scelta;
	switch(scelta)
	{
		case 1:
			quickSort(num, dimensione, compara[0]);
			break;
		
		case 2:	
			quickSort(num, dimensione, compara[1]);
			break;
		
		default:
			cout << "Inserisci 1 o 2! ";	
	}
	
	//Stampa dell'array ordinato
	for(int i=0; i<dimensione; i++)
	
		cout << num[i] << setw(3);
	
}

//Funzione che dà inizio all'ordinamento
void quickSort(int array[], const size_t &arraySize, bool (*compare)(const int &, const int &))
{
	
	if(arraySize>1)
		
		partition(array, 0, arraySize-1, compare);
}

void partition(int array[], const size_t begin, const size_t &end, bool (*compare)(const int &, const int &))
{
	
	//Primo elemento come pivot
	int pivot=begin;
	int i=end;
	
	//Trova la posizione finale del pivot
	while(i!=pivot)
	{
		
		if(i>pivot ? (*compare)(array[pivot], array[i]) : (*compare)(array[i], array[pivot]))
		{
			
			swap(array[pivot], array[i]);
			swap(pivot, i);
		}
		
		
		i>pivot ? --i : ++i;
			
	}
	
	//Partiziona in due l'array in modo ricorsivo
	if(pivot>begin)
		
		partition(array, begin, pivot-1, compare);
	
	if(pivot<end)
	
		partition(array, pivot+1, end, compare);
	
			
}

//Metodo che scambia due valori (funzione inline)
inline void swap(int &value1, int &value2)
{
	
	int temp;
	temp=value1;
	value1=value2;
	value2=temp;
	
}