Attributi degli algoritmi di ordinamento

• Ordinamento interno e ordinamento esterno: Se il file da ordinare, o la struttura dati, puòsere contenuto in memoria, il metodo viene detto interno.
• Algoritmo inplace: Un algoritmo si dice "in place" quando non crea una copia dell'input per raggiungere l'obiettivo.
• Algoritmo stabile: Un metodo di ordinamento si dice stabile se preserva l'ordine relativo dei dati con chiavi uguali all'interno del file da ordinare.
• Algoritmo online: L'algoritmo può operare anche su dati forniti "uno alla volta" anziché "tutti insieme"

• Implementazioni di esempio  C based (fonte: www.geeksforgeeks.com)  C based  Pascal based
• Kit  Pascal based  C based  C++ STL based
• Implementazione  Pascal based  C based  C++ STL based (template)  C++ STL based (no template)
• Time  Pascal based  C based  C++ STL based  Fortran based  Java based

Alcune helper functions

(* Linguaggio Pascal *)
const	MAX = 7;
type	myarray = array [0..MAX-1] of real;
var	nCompare, nMove;

function isSorted(n: word; var a: myarray): boolean;
var	i: word;
begin
	isSorted := true;
	for i := MIN to MAX do
		if (a[i-1]>a[i]) then
			isSorted := false;
end;

procedure analysis(n: word);
begin
  // ...
end;

var	a: myarray = (1.1, -0.7, -0.4, -0.1, 0.2, 0.5, 0.9);
begin
	nCompare := 0;
	nMove := 0;
	T0 := Time;
	case 1 of
	1:	insertionSort(length(a), a);
	2:	selectionSort(length(a), a);
	3:	swapSort(length(a), a);
	7:	mergeSort(length(a), a);
	end;
	T1 := Time;
	writeln('elapsed time: ', FormatDateTime('NN:SS.ZZZ', T1-T0));
	if not isSorted(length(a), a) then
		writeln('algoritmo ordinamento errato');
	for i := 0 to length(a)-1 do
		write(a[i]:5:1);
	writeln();
	writeln('nCompare/nMove: ', nCompare:9, nMove:9);

	analysis(max);
end.

void analysis(const unsigned n) {
	printf("Insertion (min): %5u %5u\n", (n-1),       2*(n-1));
	printf("Insertion (avg): %5u %5u\n", (n²+n-2)/4, (n*n+9*n-10)/4);
	printf("Insertion (max): %5u %5u\n", (n²+n)/2-1, (n*n+3*n-4)/2);

	printf("Selection (min): %5u %5u\n", (n²-n)/2,   3*(n-1));
	printf("Selection (avg): %5u %5u\n", (n²-n)/2,   (int)(n*(log(n)+0.577)));
	printf("Selection (max): %5u %5u\n", (n²-n)/2,   (n*n/4+3*(n-1)));

	printf("Bubble    (min): %5u %5u\n", (n²-n)/2,   0);
	printf("Bubble    (avg): %5u %5u\n", (n²-n)/2,   (n*n-n)*3/4/3);
	printf("Bubble    (max): %5u %5u\n", (n²-n)/2,   (n*n-n)*3/2);
}

/* Linguaggio C++ */
#include
#include
#include
#include
bool isSorted(std::vector vet[]) {
	return std::is_sorted(vet.begin(), vet.end());
}
void analysis(const unsigned n) {
	std::cout << "Insertion (min): " << (n-1)       << 2*(n-1)         << std::endl;
	std::cout << "Insertion (avg): " << (n*n+n-2)/4 << (n*n+9*n-10)/4) << std::endl;
	std::cout << "Insertion (max): " << (n*n+n)/2-1 << (n*n+3*n-4)/2   << std::endl;

	std::cout << "Selection (min): " << (n*n-n)/2   << 3*(n-1)                 << std::endl;
	std::cout << "Selection (avg): " << (n*n-n)/2   << (int)(n*(log(n)+0.577)) << std::endl;
	std::cout << "Selection (max): " << (n*n-n)/2   << (n*n/4+3*(n-1))         << std::endl;

	std::cout << "Bubble    (min): " << (n*n-n)/2   << 0               << std::endl;
	std::cout << "Bubble    (avg): " << (n*n-n)/2   << (n*n-n)*3/4/3   << std::endl;
	std::cout << "Bubble    (max): " << (n*n-n)/2   << (n*n-n)*3/2     << std::endl;
}
unsigned nCompare, nMove;
int main() {
	nCompare = 0;
	nMove = 0;
	std::vector a { 0.9, 0.5, 0.2, -0.1, -0.4, -0.7, -1.1, };
	switch (1) {
	case 1:	insertion_sort(a.begin(), a.end());
		break;
	case 2:	selection_sort(a.begin(), a.end());
		break;
	case 3:	swap_sort(a.begin(), a.end());
		break;
	case 5:	heap_sort(a.begin(), a.end());
		break;
	case 6:	quick_sort(a.begin(), a.end());
		break;
	case 7:	merge_sort(a.begin(), a.end());
		break;
	}
	if (!isSorted(a))
		std::cerr << "algoritmo ordinamento errato" << std::endl;

//	copy(std::begin(a), std::end(a), std::ostream_iterator(std::cout, " "));
//	std::cout << std::endl;

	for (auto i = a.begin(); i != a.end(); ++i)
		std::cout << std::setw(5) << *i;
	std::cout << std::endl;

	std::cout << "nCompare: " << nCompare << ", nMove: " << nMove << std::endl;

	analysis(max);

	return 0;
}

Algoritmi semplici

• Insertion sort(inserimento diretto): partiziono l'array in due parti: a sinistra quella ordinata, a destra quella non ordinata. Un array di un solo elemento è ordinato. Sposto poi gli elementi uno alla volta dalla parte non ordinata alla parte ordinata. Molto adatto per le liste.
  • InPlace: Yes
  • Stable: Yes
  • Online: Yes
  • Worst/Average/Best case time complexity: n²(reverse sorted)/n²/n²(already sorted)

  (* Linguaggio Pascal *)
  procedure insertionSort(n: word; var a: myarray);
  var	i: word;
  	key: real;
  begin
  	// l'array partizionato, a sx ordinato e a dx non ordinato
  	for i := 1 to n-1 do
  	begin
  		key := a[i];
  		inc(nMove);
  		// inserisci key al posto giusto nel sottoarray a[MIN..i] mediante shifting a DX
  		j := i;
  		while (j > 0) and (a[j-1] > key) do
  		begin
  			inc(nCompare); // conteggio confronti non corretto
  			a[j] := a[j-1];
  			inc(nMove);
  			dec(j);
  		end;
  		a[j] = key;
  		inc(nMove);
  	end;
  end;
  
  Cmin/avg/max =   (n-1) ---    (n²+n-2)/4 ---   (n²+n)/2-1
  Mmin/avg/max = 2*(n-1) --- (n²+9*n-10)/4 --- (n²+3*n-4)/2
  
  C=½*(n²+n)/2-1
  M=½*(n²+3n-4)
  O(n²)
  

  fonte
• Selection sort(selezione diretta): Cerco l'elemento più piccolo su tutto l'array, poi scambio tale elemento in posizione 1. Cerco l'elemento più piccolo tra gli elementi da 2 ad n, poi scambio tale elemento con quello in seconda posizione. ecc
  • InPlace: Yes
  • Stable: No
  • Online: No
  • Worst/Average/Best case time complexity: n²/n²/n² (two nested loops)

  (* Linguaggio Pascal *)
  procedure selectionSort(n: word; var a: myarray);
  var	i, j, k: word;
  begin
  {$IF 0}
  	// array partizionato, a sx ordinato e a dx non ordinato
  	for i := 0 to n-2 do
  	begin
  		// k := indice del valore minimo del sottoarray a[i..MAX]
  		k := i;
  		key := a[i];
  		for j := i+1 to n-1 do
  		begin
  			inc(nCompare);
  			if (key > a[j]) then
  			begin
  				k := j;
  				key := a[j];
  			end;
  		end;
  		// .
  		scambia(a[i], a[k]);
  		inc(nMove);
  	end;
  {$ELSE}
  	// array partizionato, a dx ordinato e a sx non ordinato
  	for i := n-1 downto 1 do
  	begin
  		// k := indice del valore massimo del sottoarray a[MIN..i]
  		k := i;
  		key := a[i];
  		for j := i-1 downto 0 do
  		begin
  			inc(nCompare);
  			if (key < a[j]) then
  			begin
  				k := j;
  				key := a[j];
  			end;
  		end;
  		// .
  		scambia(a[i], a[k]);
  		inc(nMove);
  	end;
  {$ENDIF}
  

  Cmin/avg/max = (n²-n)/2
  Mmin/avg/max = 3*(n-1) --- (int)(n*(log(n)+0.577)) --- n²/4+3*(n-1)
  
  C=½*(n²-n)
  M=n(log n+g)
  O(n²)
  

  fonte
• Bubble sort: Confronto l'ultimo elemento con il penultimo e se necessario li scambio. Confronto il penultimo col terzultimo e così via. Se non si sono verificati scambi, allora l'array è in ordine.
  • InPlace: Yes
  • Stable: Yes
  • Online: Yes
  • Worst/Average/Best case time complexity: n²(reverse sorted)/n²/n(already sorted)

  (* Linguaggio Pascal *)
  procedure swapSort(n: word; var a: myarray);
  var	i, j: word;
  	swapped: boolean;
  begin
  {$IF 0}
  	// ordino a partire dal fondo
  	for i := MIN+1 to MAX do
  	begin
  		swapped := false;
  		for j := MAX downto i do
  			if (a[j-1] > a[j]) then
  			begin
  				scambia(a[j-1], a[j]);
  				swapped := true;
  			end;
  		if (not swapped) then
  			break;
  	end;
  {$ELSE}
  	// ordino a partire dall'inizio
  	for i := MAX-1 downto MIN do
  	begin
  		swapped := false;
  		for j := MIN to i do
  			if (a[j] > a[j+1]) then
  			begin
  				scambia(a[j], a[j+1]);
  				swapped := true;
  			end;
  		if (not swapped) then
  			break;
  	end;
  {$ENDIF}
  end;
  
  Cmin/avg/max = (n²-n)/2
  Mmin/avg/max = 0 --- (n²-n)*3/4 --- (n²-n)*3/2
  
  C=½*(n²-n)
  M=3*½*(n²-n)
  O(n²)
  

  fonte

Algoritmi evoluti

• Shell sort: ...
  • InPlace: Yes
  • Stable: No
  • Worst/Average/Best case time complexity: n²/n²

  /* Linguaggio C */
  int shellSort(int arr[], int n) {
  	// Start with a big gap, then reduce the gap
  	for (int gap = n/2; gap > 0; gap /= 2) {
  		// Do a gapped insertion sort for this gap size.
  		// The first gap elements a[0..gap-1] are already in gapped order
  		// keep adding one more element until the entire array is
  		// gap sorted 
  		for (int i = gap; i < n; i += 1) {
  			// add a[i] to the elements that have been gap sorted
  			// save a[i] in temp and make a hole at position i
  			int temp = arr[i];
  
  			// shift earlier gap-sorted elements up until the correct 
  			// location for a[i] is found
  			int j;            
  			for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
  				arr[j] = arr[j - gap];
             
  			//  put temp (the original a[i]) in its correct location
  			arr[j] = temp;
  		}
  	}
  	return 0;
  }
  O(n^1.2)
  

• Heapsort: Prima di tutto, tramite spostamenti, creo una struttura heap(i due figli di un nodo devono essere maggiori del padre). Successivamente uso la struttura heap per ridurre il numero di confronti.
  • InPlace: Yes
  • Stable: No
  • Worst/Average/Best case time complexity: n²/n²

  /* Linguaggio C */
  // To heapify a subtree rooted with node i which is
  // an index in arr[]. n is size of heap
  void heapify(int arr[], int n, int i)
  {
      int largest = i;  // Initialize largest as root
      int l = 2*i + 1;  // left = 2*i + 1
      int r = 2*i + 2;  // right = 2*i + 2
   
      // If left child is larger than root
      if (l < n && arr[l] > arr[largest])
          largest = l;
   
      // If right child is larger than largest so far
      if (r < n && arr[r] > arr[largest])
          largest = r;
   
      // If largest is not root
      if (largest != i)
      {
          swap(arr[i], arr[largest]);
   
          // Recursively heapify the affected sub-tree
          heapify(arr, n, largest);
      }
  }
   
  // main function to do heap sort
  void heapSort(int arr[], int n)
  {
      // Build heap (rearrange array)
      for (int i = n / 2 - 1; i >= 0; i--)
          heapify(arr, n, i);
   
      // One by one extract an element from heap
      for (int i=n-1; i>=0; i--)
      {
          // Move current root to end
          swap(arr[0], arr[i]);
   
          // call max heapify on the reduced heap
          heapify(arr, i, 0);
      }
  }
  

  O(n log n)
  

  fonte
• Quicksort: ...
  • InPlace: Yes
  • Stable: No
  • Worst/Average/Best case time complexity: n²/n²

  /* Linguaggio C */
  /* This function takes last element as pivot, places
     the pivot element at its correct position in sorted
      array, and places all smaller (smaller than pivot)
     to left of pivot and all greater elements to right
     of pivot */
  int partition (int arr[], int low, int high)
  {
      int pivot = arr[high];    // pivot
      int i = (low - 1);  // Index of smaller element
   
      for (int j = low; j <= high- 1; j++)
      {
          // If current element is smaller than or
          // equal to pivot
          if (arr[j] <= pivot)
          {
              i++;    // increment index of smaller element
              swap(&arr[i], &arr[j]);
          }
      }
      swap(&arr[i + 1], &arr[high]);
      return (i + 1);
  }
   
  /* The main function that implements QuickSort
   arr[] --> Array to be sorted,
    low  --> Starting index,
    high  --> Ending index */
  void quickSort(int arr[], int low, int high)
  {
      if (low < high)
      {
          /* pi is partitioning index, arr[p] is now
             at right place */
          int pi = partition(arr, low, high);
   
          // Separately sort elements before
          // partition and after partition
          quickSort(arr, low, pi - 1);
          quickSort(arr, pi + 1, high);
      }
  }
  

  O(n log n)
  

  fonte
• Mergesort: ...
  • InPlace: No
  • Stable: Yes
  • Worst/Average/Best case time complexity: n*log(n)

  /* Linguaggio Pascal */
  
  /* Linguaggio C */
  void merge (float *a, unsigned n, unsigned m) {
  	float *x = (float *)malloc(n * sizeof (float));
  	for (unsigned i = 0, j = m, k = 0; k < n; k++) {
  		x[k] = j == n      ? a[i++]
  			: i == m      ? a[j++]
  			: a[j] < a[i] ? a[j++]
  			:               a[i++];
  	}
  	for (unsigned i = 0; i < n; i++)
  		a[i] = x[i];
  	free(x);
  }
  void merge_sort (float *a, unsigned n) {
  	if (n < 2)
  		return;
  	unsigned m = n / 2;
  	merge_sort(a, m);
  	merge_sort(a + m, n - m);
  	merge(a, n, m);
  }
  

  O(n log n)
  

  fonte