Perché Quicksort è chiamato "Quicksort"?

9

Il punto di questa domanda non è di discutere i meriti di questo su qualsiasi altro algoritmo di ordinamento - certamente ci sono molte altre domande che lo fanno. Questa domanda riguarda il nome. Perché Quicksort viene chiamato "Quicksort"? Certo, è "veloce", la maggior parte delle volte, ma non sempre. La possibilità di degenerare a O (N ^ 2) è ben nota. Ci sono varie modifiche a Quicksort che mitigano questo problema, ma quelle che portano il caso peggiore a un O garantito (n log n) non sono generalmente chiamate Quicksort. (ad esempio Introsort).

Mi chiedo solo perché di tutti i ben noti algoritmi di ordinamento, questo è l'unico meritevole del nome "quick", che descrive non come funziona l'algoritmo, ma quanto è veloce (di solito). Mergesort è chiamato così perché unisce i dati. Heapsort viene chiamato così perché utilizza un heap. Introsort prende il nome da "Introspective", poiché monitora le proprie prestazioni per decidere quando passare da Quicksort a Heapsort. Allo stesso modo per tutti quelli più lenti - Bubblesort, Insertion sort, Selection sort, ecc. Sono tutti chiamati per come funzionano. L'unica altra eccezione che mi viene in mente è "Bogosort", che in realtà è solo uno scherzo che nessuno in realtà utilizza nella pratica. Perché Quicksort non ha chiamato qualcosa di più descrittivo, come "Partition sort" o "Pivot sort", che descrive cosa fa effettivamente? Non è nemmeno il caso di "prima arriva qui". Mergesort è stato sviluppato 15 anni prima di Quicksort. (1945 e 1960 rispettivamente secondo Wikipedia)

Immagino che questa sia davvero una questione di storia più che di programmazione. Sono solo curioso di sapere come è stato il nome - è stato solo un buon marketing?

    
posta Darrel Hoffman 28.06.2013 - 16:15
fonte

3 risposte

13

Nel 1962 la ricerca sugli algoritmi di ordinamento non era così avanzata come oggi e lo scienziato informatico Tony Hoare trovato un nuovo algoritmo che è stato più veloce dell'altro quindi ha pubblicato un documento chiamato Quicksort e come la carta è stata citata il titolo rimasto.

Citando l'abstract:

A description is given of a new method of sorting in the random-access store of a computer. The method compares very favourably with other known methods in speed, in economy of storage, and in ease of programming. Certain refinements of the method, which may be useful in the optimization of inner loops, are described in the second part of the paper.

    
risposta data 28.06.2013 - 16:25
fonte
0

Credo che in origine si chiamasse Hoare Sort dopo l'inventore, ma il nome è stato modificato abbastanza presto perché Hoare sembrava un po 'troppo vicino alla puttana in inglese. Per quanto riguarda il motivo per cui hanno scelto "veloce" invece di qualcos'altro, non ne sono sicuro.

    
risposta data 28.06.2013 - 19:06
fonte
-1

Credo che sia perché, al momento in cui è stato inventato, è stato molto più veloce di tutti (o, piuttosto, la maggior parte, poiché la velocità dipende anche dal tipo di dati e in alcuni casi l'altro algoritmo diventa molto più veloce di Quicksort ) degli algoritmi là fuori.

Quindi sì, è storico (non conosco precisamente quella storia, comunque ...)

Ma sono d'accordo sul fatto che il suo nome dovrebbe contenere un suggerimento dell'algoritmo ...

    
risposta data 28.06.2013 - 16:23
fonte

Leggi altre domande sui tag