[C] MergeSort vs QuickSort

[Gil Mour]

Mi sono documentato su siti di varie università sulle complessità dei due algoritmi, e sembra essere dimostrato che msort è piu efficiente di qsort.
Per la precisione, sembra che msort abbia complessita O(n logn) mentre per il qsort dovrebbe valere O(n*n) (il tutto considerato nel caso peggiore).

Ora, che io sappia, in math.h dei due algoritmi è implementato solo il qsort.
Dopo varie ricerche ho trovato questa implementazione del msort che sembra abbastanza snella e congruente con l'algoritmo

Allora ho testato i due algoritmi con vettori generati casualmente di pari lunghezza ed i risultati vanno nella direzione opposta a quella indicata dai principi teorici: qsort sembra ordinare il vettore in un tempo inferiore alla metà di quanto impiega questa implementazione di msort.

Le spiegazioni che mi sono dato di questo fatto sono diverse:
1. il qsort definito in math.h in realtà non è un vero e proprio quick sort ma un algoritmo piu prestante
2. l'implementazione di msort che ho utilizzato non è una buona implementazione (tuttavia, è la migliore che sono riuscito a procurarmi su internet)

Avete qualche considerazione illuminante in proposito?

[Insaponata]

Si: che il Quick-Sort è il più veloce algoritmo di ordinamento che esiste. Non è vero che Msort è migliore di Qsort: anche se la complessità di Qsort nel caso peggiore è quadratica, questo caso peggiore si verifica rarissimamente. In più si dimostra che il caso medio di entrambi gli algoritmi è O(n*log(n)), ma il Qsort ha un fattore proporzionale (che si nascone nella notazione o grande) inferiore rispetto a quello dell'Msort; quindi il quick sort è più veloce.
Se gli appunti che hai trovato son buoni, dovresti trovare anche questa dimostrazione.
Ciao.

[anx721]

è appunto solo un fatto di probabilità..ovvio che se parli di complessita in generale il quicksorto è n^2 perche ci sono dei casi in cui raggiunge tale valore, ad esempio se il vettore è gia ordinato, o ordinato al contrario; pero se il vettore è lungo n ci sono n! possibili diverse permutazioni degli elementi, e solo in una frazione piccolisima di queste il quicksort raggiunge il caso peggiore, nella pratica è l'algoritmo piu veloce.

[Insaponata]

La mia risposta + quella di anx721 pongono fine alla questione :-) !
ciao.

[infinitejustice]

Il merge ha la stessa complessità asintotica del quick, quindi nn è certo in base alla velocità che il quick è preferibile.
Mergesort ha la sola pecca di non ordinare sul posto (richiede spazio extra) ed è preferibile ad esempio per ordinare liste.

Questo è mergesort (corretto)

void merge(int *array, int l, int m, int r){

	int i, j, k, aux[nr];

    for (i = m+1; i > l; i--) aux[i-1] = array[i-1];
    for (j = m; j < r; j++) aux[r+m-j] = array[j+1];
    for (k = l; k <= r; k++)
       if(aux[i] <= aux[j])
          array[k] = aux[i++];
	  else
		  array[k] = aux[j--];
}

void mergesort(int *array, int l, int r){

	int m = (r+l)/2;
    if(r <= l)
		return;

    mergesort(array, l, m);
    mergesort(array, m+1, r);
    merge(array, l, m, r);
}

questo è merge applicato alle liste

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct linked{
	int value;
	struct linked *next;
	} *first = NULL, *new;


void add(int);
void show(void);
struct linked * merge(struct linked *, struct linked *);
struct linked *mergesort(struct linked *);


void main(){

	add(25);
	show();
	first = mergesort(first);
	show();
}


void add(int nr){

	srand(time(NULL));

	while(nr--){
		if(!(new = (struct linked *)malloc(sizeof(struct linked))))
			abort();
		(*(new)).value = rand()%100;
		(*(new)).next = NULL;
		(*(new)).next = first;
		first = new;
		}
}


struct linked * merge(struct linked *a, struct linked *b){

	struct linked head;
	struct linked *node = &head;

	while((a != NULL) && (b != NULL))
		if(a->value <= b->value){
			node->next = a;
			node = a;
			a = a->next;
			}
		else{
			node->next = b;
			node = b;
			b = b->next;
			}
		node->next = (a == NULL) ? b : a;

return head.next;
}


struct linked *mergesort(struct linked *node){

	struct linked *a = node;
	struct linked *b = node->next;

	if(node == NULL || node->next ==  NULL)
		return node;

	while((b != NULL) && (b->next != NULL)){
		node = node->next;
		b = b->next;
		}

	b = node->next;
	node->next = NULL;

return merge(mergesort(a), mergesort(b));
}

void show(){

	struct linked *temp;
	for(temp = first; temp->next != NULL; temp = temp->next)
		printf("%d ", temp->value);
	printf("\n");
}

Esistono inoltre algoritmi di sorting in grado di ordinare in tempo lineare (radix, counting) ma si applicano solo a casi specifici (quindi quick non è il piu veloce)





edit: ho incollato i codici perche cliccando sui link aggiunge degli spazi bianchi e nn trova le pagine

[Gil Mour]

quali sono i casi specifici cui ti riferisci per questi algoritmi a complessita lineare?

[anx721]

Il counting sort ha complessità lineare rispetto alla lunghezza N del vettore da ordinare se il numero di elementi tra il minimo e il massimo del vettore è lineare in N. Esempio: devi ordinare un vettore di 100 interi; se tali interi variano tra 0 e 100 il counting sort effettuerà k*100 operazioni; se gli elementi variano tra 0 e 1000.000 il counting sort effettuerà k*1000.000 di operazioni...nella pratica sono rari i casi in cui puo essere aplicato.