Il bubble sort è il meno efficiente di Big-O? Se la risposta è no, allora qual è l'algoritmo di ordinamento meno efficiente?
Vado a favore di BogoSort per essere il peggiore se esegui il confronto solo in base alle prestazioni peggiori!
Visita questo wiki link per avere un'idea generale dei confronti del tempo di esecuzione di diversi tipi. Le prestazioni di ordinamento dipendono sempre molto dai dati e dallo scenario. È difficile dire che uno sia sempre il peggiore.
A corto di intenzionalmente perverso, ce n'è ancora uno che è più lento del bubble sort, ma ha una vera ragione per esistere (sorta, comunque). Knuth V3 (in uno degli esercizi) mostra un algoritmo ottimizzato per ridurre al minimo le dimensioni del codice. Produce un codice estremamente piccolo - a spese oh-so-margin della complessità di O (N 3 ).
Anche se le probabilità di incontrarlo effettivamente con l'hardware moderno sono inesistenti, vale anche la pena ricordare che proprio sotto l'insieme corretto di circostanze Bubble sort non è davvero un algoritmo così terribile - piuttosto il contrario, all'interno del corretto esatto serie di vincoli sull'hardware è dimostrabile non solo come buono come qualsiasi altra cosa, ma si avvicina asintoticamente alle migliori prestazioni di qualsiasi algoritmo possibile.
In effetti, quella prova sembra essere la ragione principale per cui è diventato ragionevolmente noto - è praticamente il primo algoritmo per il quale una tale prova formale è mai stata pubblicata. OTOH, è quasi perduto nella notte dei tempi e la maggior parte delle persone che lo insegnano non hanno idea del motivo per cui è stata originariamente conosciuta. Invece, per quanto posso dire, la gente lo insegna solo perché l'ha imparato, e per qualche ragione pensa che sia importante per la prossima generazione impararlo, anche se la ragione della sua esistenza è scomparsa molto tempo prima che la maggior parte di loro fosse nata.
Se intendi includere algoritmi intenzionalmente perversi, allora il bogobogosort è molto peggio del semplice bogosort. Un semplice bogosort ha una complessità di circa O (N * N!). Il bogobogosort ha una complessità di circa O (N N-k ). Per mettere questo in prospettiva, bogosort può ordinare 10 elementi in pochi minuti (o così). Il numero di operazioni necessarie per un bogobogosort cresce così velocemente che, per quanto ne so, il maggior numero di oggetti che qualcuno abbia mai ordinato è 6 (i tentativi sono stati fatti a 7, ma, almeno a mia conoscenza, tutti questi i tentativi sono stati terminati prima del completamento (anche se, ammetto che di solito è solo dopo un giorno o due).
La velocità di ogni particolare algoritmo di ordinamento dipende da diversi fattori come l'ordine di input e la distribuzione delle chiavi. In molti casi il bubble sort è piuttosto lento, ma ci sono alcune condizioni in cui è molto veloce.
Esiste un'animazione di confronto algoritmo di ordinamento su questo sito:
L'ordinamento di Bozo è O (n!)! È fatto selezionando a caso due elementi scambiandoli e controllando se l'elenco è ordinato.
Se sai che i tuoi dati sono quasi già ordinati e che solo pochi elementi sono fuori posto, bubble sort diventa circa O (c * N) tempo, dove c è il numero di elementi fuori luogo. In quel caso sarà effettivamente più veloce della maggior parte degli altri tipi. Pessimo caso peggiore, buon caso.
Leggi altre domande sui tag algorithms sorting speed