Ordinamento

L'ordinamento, in generale, è un concetto in cui gli elementi di un contenitore vengono riordinati secondo un ordine logico.

L'ordinamento è una delle tecniche più basilari e fondamentali applicate ai dati tramite le funzioni. Ciò significa che l'ordinamento ci permette di disporre una sequenza di elementi nel modo che desideriamo, seguendo un ordine logico.

Gli algoritmi di ordinamento aiutano a manipolare i dati e a risolvere molti problemi matematici e di programmazione.

*Per utilizzare i metodi, dobbiamo includere il file header algorithm all'inizio del nostro file C++ usando #include <algorithm>.

Imparerai a conoscere le funzioni integrate della libreria di algoritmi STL usate per ordinare i dati. 
Le tre funzioni che studieremo sono:

• sort()
• is_sorted()
• partial_sort()

Metodo sort

Il metodo sort() della STL ordina il contenuto dell'intervallo specificato. Il metodo richiede un iteratore iniziale e un iteratore finale e ordina gli elementi di quell'intervallo in ordine crescente.

Possiamo usarlo in due versioni:

• sort(starting_iterator, ending_iterator) - ordina in ordine crescente l'intervallo definito dagli iteratori
• sort(starting_iterator, ending_iterator, comparing_function) - ordina l'intervallo definito dagli iteratori, ma in base alla funzione fornita come terzo parametro

vector<int> numbers = {3, 5, 1, 2, 4};

sort(numbers.begin(), numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
	cout << *i << " ";

Output:
1 2 3 4 5

Come puoi vedere dal codice qui sopra, il metodo sort() ha ordinato il vettore in ordine crescente.

bool compare(int a, int b)
{
	return a > b; // restituisce 1 se a è maggiore di b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	sort(numbers.begin(), numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
5 4 3 2 1

Come puoi vedere, abbiamo usato la seconda versione del metodo sort. Creiamo la funzione compare() in modo che restituisca true se a è maggiore di b. Questo ci permette di ordinare il vettore in ordine decrescente.

Metodo is_sorted

Il metodo is_sorted() è una funzione della STL che restituisce true o false a seconda che l'intervallo specificato sia ordinato o meno. 

Esistono anche due versioni del metodo is_sorted(), esattamente come per il metodo sort():

• is_sorted(starting_iterator, ending_iterator) - verifica se l'intervallo definito dai due iteratori è ordinato in ordine crescente; restituisce true se lo è, altrimenti restituisce false
• is_sorted(starting_iterator, ending_iterator, comparing_function) - verifica se l'intervallo definito dai due iteratori è ordinato in base alla funzione di confronto.

vector<int> numbers = {3, 5, 1, 2, 4};

cout << is_sorted(numbers.begin(), numbers.end()) << endl;

sort(numbers.begin(), numbers.end());

cout << is_sorted(numbers.begin(), numbers.end());

Output:
0
1

bool compare(int a, int b)
{
	return a > b; // restituisce 1 se a è maggiore di b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare) << endl;
	
	sort(numbers.begin(), numbers.end(), compare);
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare);

Output:
0
1

Metodo partial_sort

Il metodo parital_sort() ordina la prima metà degli elementi dell'intervallo specificato e lascia l'altra metà degli elementi com'era inizialmente. 
Ha anche due versioni:

• partial_sort(start, middle, end) - ordina l'intervallo da start a end in modo che gli elementi dall'iteratore iniziale all'iteratore middle siano ordinati in ordine crescente e che gli elementi dall'iteratore middle all'iteratore finale restino come erano inizialmente
• partial_sort(start, middle, end, compare) - ordina l'intervallo da start a end in modo che gli elementi da start a middle siano ordinati in base alla funzione di confronto e che gli elementi da middle a end restino come erano inizialmente

vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};

partial_sort(numbers.begin(), numbers.begin() + 4, numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
1 2 3 4 5 10 7

bool compare(int a, int b)
{
	return a > b; // return 1 se a è maggiore di b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};
	
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
10 7 5 1 2 3 4

Come puoi vedere, il metodo partial_sort() funziona in modo un po' diverso, ma non preoccuparti: userai raramente un ordinamento parziale. 

Per ora, ricorda cos'è l'ordinamento, impara bene i metodi sort() e is_sorted() e fai pratica a usarli.