Recentemente ho iniziato a utilizzare la libreria <vector.h> e mi chiedevo, dal momento che tutte le operazioni sono già state implementate, SE il metodo dell'algoritmo di ordinamento è il più efficiente. Tutto funziona perfettamente, non c'è dubbio, ma dovrei preoccuparmi delle sue prestazioni?
Se voglio ordinare fino a 6-7 milioni di numeri, dovrei implementare il mio metodo di ordinamento usando l'ordinamento rapido?
Nella maggior parte delle librerie, std::sort è implementato come un introsort, quindi a meno che tu non voglia fare del male alle prestazioni nel caso peggiore (molto), quasi certamente non vuoi usare Quicksort. La mia esperienza indica che un Quicksort laminato in casa raramente migliorerà sensibilmente le prestazioni in ogni caso.
Il motivo principale per passare a qualcos'altro sarebbe ottenere qualcosa come la stabilità (nel qual caso vuoi std::stable_sort ) o la capacità di lavorare con i dati che non rientrano nella RAM (nel qual caso potresti voler guarda STXXL ), non per prestazioni semplici.
È difficile essere definitivi senza conoscere il tuo caso d'uso in dettaglio, ma come regola generale;
Non ottimizzare presto
Per prima cosa implementa la soluzione più semplice, più leggibile e gestibile, quindi esegui il benchmark. Spesso sarà abbastanza veloce. Dovresti solo preoccuparti dell'ottimizzazione quando c'è un problema e quando hai fatto abbastanza analisi comparative per sapere dove si trova il problema.
Gli algoritmi di ordinamento si differenziano in base alle determinate proprietà della raccolta dati.
Dici di aver appena iniziato a usare, quindi non è probabile che tu scriva algoritmi di ordinamento più veloci delle persone che hanno creato C ++ e le sue librerie. Utilizza le librerie standard.
È improbabile che tu possa creare un ordinamento più veloce di std :: sort nella maggior parte dei casi. è anche più veloce del C qsort () in molti casi.
Leggi altre domande sui tag c++ algorithms sorting stl