Algoritmi di ordinamento di ordine n²

Il problema dell’ordinamento consiste nell’ordinare in senso crescente o decrescente tutti gli elementi di un dato array ordinato.

Vi sono vari tipi di algoritmi di ordinamento (sorting algorithm), l’efficienza di ciascuno di essi è data teoricamente contando il numero di confronti effettuati.

Tra gli algoritmi più semplici vedremo il BubbleSort, il SelectionSort e l’InsertionSort. Sono tutti e tre di ordine n², cioè è necessario (approssimativamente) eseguire n² controlli per ordinare un array di n elementi.

Innanzitutto faremo uso della funzione swap, che scambia tra loro due valori di un dato array:

public static void swap(int array[], int primo, int secondo)
 {
	int tmp;
	tmp=array[primo];
	array[primo]=array[secondo];
	array[secondo]=tmp;
}

Il BubbleSort passa in rassegna tutti i valori dell’array diverse volte.
Durante ogni scansione vengono confrontate tutte le coppie di elementi contigui: se, in una coppia, il primo valore è minore o uguale al secondo, gli elementi vengono lasciati al loro posto; se, invece, il primo valore è maggiore del secondo i due elementi vengono scambiati di posto nell’array, tramite la funzione swap.
Tutto ciò si ripete finchè l’array non è ordinato:

public static void BubbleSort(int array[])
{
	for (int x=1; x<array.length; x++)
		for (int i=0; i<array.length-x; i++)
			if (array[i]>array[i+1])
				swap(array, i, i+1);
}

Il SelectionSort ricerca il più piccolo valore dell’array e lo scambia con l’elemento nella prima posizione dell’array. Dopo di che ricerca l’ennesimo valore più piccolo nell’array e scambia tale elemento con quello nell’ennesima posizione dell’array e ripete questo procedimento finché l’intero array è ordinato.

public static void SelectionSort(int array[])
{
	int min;

	for (int index=0; index<array.length-1; index++)
	{
		min=index;
		for (int i=index+1; i<array.length; i++)
			if (array[i]<array[min])
				min=i;
		swap(array, index, min);
	}
}

L’InsertionSort sposta ogni elemento in un sotto-array ordinato, considerando un elemnto alla volta lo inserisce nella posizione corretta tra quelli già considerati e fa scorrere di posizione tutto il resto:

public static void InsertionSort(int array[])
{
	for (int index=1; index<array.length; index++)
	{
		int key=array[index];
		int position=index;

		while (position>0 && key<array[position-1])
		{
			array[position]=array[position-1];
			position--;
		}

		array[position]=key;
	}
}