Per quanto riguarda l'algoritmo di ordinamento con shell

Question

Sto leggendo l'abbreviazione di algoritmi. È menzionato in shell ordinamento come di seguito

Un'importante proprietà di Shellsort (che affermiamo senza prove) è che un file (H subscipt k) che è quindi (H subsciprt (K-1)) rimane HK-1 ordinato HK. Se non fosse così, l'algoritmo sarebbe probabilmente di scarso valore, poiché il lavoro svolto dalle fasi iniziali sarebbe annullato dalle fasi successive.

La mia domanda è cosa significa l'autore per la dichiarazione di cui sopra?

Grazie!

Answer 1

Shell Sort è un algoritmo di smistamento multi-pass. Funziona ordinando un sottoinsieme dell'array con un determinato valore di "passo" intero k, cioè accedere solo a tutti kth elemento nell'array.

Inizialmente viene utilizzato un valore elevato per il passo, sui passaggi successivi questo valore di passo viene ridotto fino a quando il passaggio finale non viene eseguito con un passo di 1 (che in genere è solo una fase di ordinamento di inserimento standard) e l'array è completamente ordinato.

L'affermazione che hai chiesto semplicemente dice che qualsiasi ordinamento che è stato fatto su passaggi precedenti (valori di passo maggiore) è preservato da passaggi successivi (valori di passo più piccoli). Se non fosse così, non ci sarebbe alcun punto nell'approccio multi-pass utilizzato dall'ordinamento della shell.

Spero che sia di aiuto.