Numero medio di confronti per algoritmi di ordinamento

Question

Numero medio di confronti per algoritmi di ordinamento

#1 da (3 voti)
#2 da (0 voti)

1

Ho bisogno di scrivere algoritmi di ordinamento diversi come

bubblesort
InsertionSort
SelectionSort
QUICKSORT
Mergesort

E quantifica il numero medio di confronti per numero di N (media tra test N!). Ma ho bisogno di alcuni risultati finali per confrontare i risultati del mio programma.

C'è qualche tabella che fornisce la media dei confronti di questi algoritmi per alcuni N numeri?

Questo è quello che ho ottenuto per la media della lunghezza dell'array 10:

    Selection sort: 63
    Bubble sort: 49.4144
    Insertion sort: 31.5
    Merge sort: 31.6667
    Quick sort: 30.7706

algorithms sorting measurement

posta zahmati 24.04.2015 - 00:20

fonte

2 risposte

3

Una grande risorsa: link

Posso dirti subito che:

Bubble Sort è nel peggiore dei casi, O (N ²)
L'ordinamento di inserimento è nel peggiore dei casi, O (N ²)
Selezione L'ordinamento è nel peggiore dei casi, O (N ²)
L'ordinamento rapido è nel peggiore dei casi, O (N ²), tuttavia è tipicamente O (n log n)
Unisci Ordina è nel peggiore dei casi, O (n log n)

risposta data 24.04.2015 - 02:45

fonte

Leggi altre domande sui tag algorithms sorting measurement

One Enum vs Enum multipli Quando il set di risultati non è importante dovrebbero essere usati Join sinistro o Join interno

score 0 · Accepted Answer

Is there any table giving the average of comparisons of these algorithms for a few N numbers

Il numero esatto di confronti necessari può dipendere dall'implementazione specifica dell'algoritmo, non dall'algoritmo stesso, e così pure dal numero medio. Quindi, anche se trovi qualcosa di simile a quello che hai richiesto, trovo molto improbabile che tu possa confrontarlo direttamente con la tua implementazione degli algoritmi.