Ricorsione infinita in quicksort JavaScript?

Question

Questo è il codice quicksort che ho scritto. La funzione non funziona perché non può raggiungere il caso base. Se registro il pivot, r e l nella console, rimangono invariati indipendentemente dal numero di volte in cui viene chiamata la funzione di ordinamento. Quindi mi chiedo se l'argomento l, r non sia realmente passato nella funzione come dati. Perchè è successo?

function sort(data){ 
    if(data.length < 2){ 
     return data; 
    } 
    else{ 
     var l = []; 
     var r = []; 
     var pivot = parseInt(data.length/2); 
     for(i=0; i<data.length; i++){ 
      if(data[i] > data[pivot]){ 
       r.push(data[i]); 
      } 
      else{ 
       l.push(data[i]); 
      } 
     } 
     return sort(l).concat(sort(r)); 
    } 
} 

Answer 1

Penso che il problema qui sia che il passaggio del partizionamento non necessariamente riduce l'array di input. Per esempio, vediamo cosa succede se provi a ordinare [1, 2]. In questo caso, l'elemento di pivot sarà l'elemento 2. Poiché 1> 2 è falso, 1 viene aggiunto all'elenco l. Poiché 2> 2 è falso, 2 viene aggiunto all'elenco l. Di conseguenza, la chiamata ricorsiva nell'elenco l avrà esattamente gli stessi argomenti della chiamata originale, causando una ricorsione infinita.

Per risolvere questo problema, provare a suddividere l'input in tre elenchi: uno di valori più piccoli, uno di valori uguali e uno di valori maggiori. Questo codice è mostrato qui:

function sort(data){ 
    if (data.length < 2){ 
    return data; 
    } else { 
    var l = []; 
    var r = []; 
    var e = []; 
    var i = 0; 
    var pivot = (data.length/2) | 0; 

    for(i = 0; i < data.length; i++) { 
     if (data[i] > data[pivot]) { 
     r.push(data[i]); 
     } else if (data[i] < data[pivot]) { 
     l.push(data[i]); 
     } else { 
     e.push(data[i]); 
     } 
    } 
    return sort(l).concat(e, sort(r)); 
    } 
} 

questa nuova versione esplicitamente raggruppa gli elementi uguali nella loro propria lista, quindi non sono ricorsivamente allineati secondo una delle due chiamate ricorsive. Gestisce anche con grazia gli elementi duplicati.

Spero che questo aiuti!

Answer 2

JavaScript passa gli oggetti per riferimento (anche gli array sono oggetti). Se si desidera passarli per valore, è necessario utilizzare la funzione di giunzione come spiegato here.

Nota che questo creerà molte copie dei tuoi dati. Probabilmente vuoi usare la funzione nativa sort().

Answer 3

Se si sceglie il valore massimo della matrice come elemento di perno, tutti i valori di data finiranno nella matrice l e nessuno in r. In questo modo la ricorsione non si fermerà mai (e manterrà , r e pivot con gli stessi valori). A meno che non si tratti di un'esercitazione cerebrale, usare data.sort() dovrebbe fare un lavoro migliore. ;)