Domanda sull'intervallo di Shellsort Java
Domanda
Devo testare l'efficienza di shellsort quando utilizzo la dimensione dell'intervallo standard e anche quando utilizzo una dimensione non standard.Il problema che riscontro è quando provo a utilizzare il mio intervallo non standard.
Questo è il mio Shellsort quando h è uguale alla dimensione dell'intervallo standard:
public void shellSort()
{
int inner, outer;
int temp;
int h = 1;
while (h <= length / 3)
{
h = h * 3 + 1;
}
while (h > 0)
{
for (outer = h; outer < length; outer++)
{
temp = data[outer];
inner = outer;
while (inner > h - 1 && data[inner - h] >= temp)
{
data[inner] = data[inner - h];
inner -= h;
}
data[inner] = temp;
}
h = (h - 1) / 3;
}
}
Ed ecco il mio tentativo di utilizzare un intervallo di numeri primi
private int[] primes = {0, 1, 3, 7, 13, 31, 97, 211, 503, 1013, 2503, 5171};
public void shellSort()
{
int inner, outer;
int temp;
int count = this.h.length - 1;
int h = 1;
h = primes[primes.length - 1] * 2 > length ? primes[primes.length - 1] : primes[primes.length - 2];
while (h > 0)
{
for (outer = h; outer < length; outer++)
{
temp = data[outer];
inner = outer;
while (inner > h - 1 && data[inner - h] >= temp)
{
data[inner] = data[inner - h];
inner -= h;
}
data[inner] = temp;
}
if(count - 1 > 0)
h = primes[count - 1];
}
}
Sto cercando di confrontare i due in base all'efficienza in tempo reale e non riesco a capire come far funzionare questo intervallo di priming.
Sto provando a testare:
- Shellsort ha prestazioni migliori di O (N ^ 2) con dimensioni degli intervalli scelte in modo appropriato
- La serie di dimensioni degli intervalli scelte è importante per ottenere un runtime migliore di O (N ^ 2)
Grazie per qualsiasi aiuto.
Soluzione
Probabilmente vorrai diminuire il valore di count
in ogni iterazione del ciclo esterno.Nel tuo codice è ancora this.h.length-1
, che è 11. Pertanto, dopo ogni iterazione del ciclo esterno hai soddisfatto la condizione if
count-1 > 0
, quindi imposti h = this.h[count-1]
, che credo sia 2503. Quindi, reinserisci il ciclo.
A proposito, chiamare l'elenco delle dimensioni degli intervalli h
impedisce seriamente la leggibilità.Dovresti chiamarlo almeno hs
.