Il quickselect dovrebbe modificare l'array di input o no?

Normalmente mi aspetto

1. The algorithm makes a copy of the input array and fiddles with the copy.

Tuttavia, potresti avere ottimi motivi per andare dall'altra parte:

1. L'array è molto grande e l'utente chiamerà la tua funzione in un loop.
   Se lo fai, assicurati di richiamarlo nella documentazione poiché è un comportamento insolito
2. L'array di input è opaco per l'utente, cioè l'utente lo ha generato chiamando una delle tue funzioni, non ha mai promesso un particolare ordine e potrebbe anche non sapere esattamente cosa c'è dentro.

In altre parole, devi determinare cosa è meglio per la tua situazione specifica .

1 o entrambi, se possibile

Quando il linguaggio consente la distinzione tra parametri formali di sola lettura e mutabili in funzioni (ad es. const riferimento in C ++, passa per tipi di array valore + riferimenti), gli usi specifici potrebbero non interessare al fatto che l'array venga eliminato.

Altrimenti, sono d'accordo con le altre risposte che i dati di riordino trasmessi rompono le aspettative e interagiscono male con il parallelismo.

Apprezzerei 2 , poiché è più flessibile: in questo modo, posso creare una copia se mi interessa dei dati di input, mentre posso semplicemente passare i dati originali se mi interessa di più efficienza.

Ovviamente è tuo compito dichiarare molto chiaramente che modifichi la sequenza di input.

Oppure, inserisci un altro modo: la selezione rapida può essere pensata come un algoritmo "ordinamento parziale" sul posto e le interfacce con questi tipi di algoritmi di solito fanno cambiano i dati di input: pensa a std::sort e std::make_heap .

Infatti, C ++ implementa effettivamente QuickSelect nella sua libreria standard (funzione std::nth_element ). Indovina un po? Cambia i dati di input;)

Salvo molto chiaramente documentato, 1 (non scherzare con l'input).

Passare un array in una funzione e cestinare i miei dati di input è un comportamento inatteso estremamente . In circostanze normali lo definirei un bug importante.

Anche se riesci a invertire l'operazione, tieni presente che ciò interrompe la sicurezza del thread (poiché anche la lettura è ora un comportamento non definito).

Modifica: se stai cercando le opzioni di ottimizzazione (e sei sicuro che sia necessario!), potresti aggiungere un parametro facoltativo alla funzione, ad esempio bool mayRearrangeArray = false . In questo modo, l'utente ha l'opzione, ma è - per impostazione predefinita - al sicuro.

La risposta in genere dipende dalla lingua che stai utilizzando e dal tipo di utenti con cui stai lavorando.

Nelle lingue in cui la performance è il re, è tipico apportare le modifiche in-situ. L'allocazione della memoria è costosa e può essere un problema su macchine con memoria limitata, quindi gli sviluppatori C (che considererei i "re" delle prestazioni) faranno sempre lo stesso. Se osservi praticamente ogni implementazione di un algoritmo di ordinamento, scoprirai che lo fanno in questo modo.

All'altro estremo, MATLAB è in genere molto più interessato alla chiarezza che alle prestazioni. Pertanto, gli algoritmi di ordinamento in MATLAB spesso restituiscono un array appena creato con i nuovi valori in esso.

Se la tua lingua supporta la modifica in-situ, ti consiglio di seguire questa strada per un motivo akappa fatto nei commenti. È banale creare un tipo che copia semplicemente l'array e poi lo passa a un ordinamento in-situ. È impossibile andare dall'altra parte, quindi, rendendo il tuo tipo in-situ, supporti più opzioni.