Approccio iterativo di Merge Sort in Javascript
Sto cercando di implementare l'ordinamento di unione in modo iterativo ma in javascript. Ho provato anche a cercare su Internet, ma sono disponibili solo in C, Python e Java. L'array che la mia funzione sta dando non è ordinato. Ho provato cose diverse ma non riesco a capire l'errore. Qualcuno può farmi notare per favore cosa sto sbagliando?
function mergeSortIterative(arr){
let sorted=[...arr];//copying the array so that original remains unchanged.
let n=sorted.length;
let currSize;
let leftStart;
for(currSize=1;currSize<=n-1;currSize=2*currSize){
for(leftStart=0;leftStart<n-1;leftStart+=2*currSize){
let mid=Math.min(leftStart+currSize-1,n-1);
let rightEnd=Math.min(leftStart+2*currSize-1,n-1);
// let left=sorted.slice(leftStart,mid);
// let right=sorted.slice(mid,rightEnd);
// sorted=mergeIterative(sorted,left,right);
mergeIterative(sorted,leftStart,mid,rightEnd);
}
}
return sorted;
}
function mergeIterative(sorted,leftStart,mid,rightEnd){
let left=sorted.slice(leftStart,mid);
let right=sorted.slice(mid,rightEnd);
let leftIndex=0,rightIndex=0,k=leftStart;
while(leftIndex<left.length && rightIndex<right.length){
//picking the lesser one
if(left[leftIndex]<=right[rightIndex]){
sorted[k]=left[leftIndex];
leftIndex++;
k++;
}
else{
sorted[k]=right[rightIndex];
rightIndex++;
k++;
}
}
while(leftIndex<left.length && k<sorted.length){
sorted[k]=left[leftIndex];
leftIndex++;
k++;
}
while(rightIndex<right.length && k<sorted.length){
sorted[k]=right[rightIndex];
rightIndex++;
k++;
}
}
Risposte
L'errore nel codice è in una definizione incoerente di cosa mid
e rightEnd
significa.
Dal codice seguente apprendiamo che questi indici puntano alla voce dopo il sottoarray precedente:
let left = sorted.slice(leftStart, mid);
let right = sorted.slice(mid, rightEnd);
Ma guardando i compiti:
let mid = Math.min(leftStart + currSize - 1, n - 1);
let rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);
... vediamo che puntano all'elemento finale del precedente sotto-array.
Puoi correggere questo in due modi, ma poiché il modo in cui slice
interpreta i suoi argomenti è il modo "standard", suggerirei di apportare la correzione nelle assegnazioni, rimuovendo tutti quelli - 1
, come segue:
let mid = Math.min(leftStart + currSize, n);
let rightEnd = Math.min(leftStart + 2 * currSize, n);
Pranav: Ho citato di seguito un algoritmo di ordinamento di unione iterativo fornito da Michael Laszlo a una domanda simile posta in precedenza: Implementazione di ordinamento di unione iterativo
function mergeSort(arr) { var sorted = arr.slice(), n = sorted.length, buffer = new Array(n); for (var size = 1; size < n; size *= 2) { for (var leftStart = 0; leftStart < n; leftStart += 2*size) { var left = leftStart, right = Math.min(left + size, n), leftLimit = right, rightLimit = Math.min(right + size, n), i = left; while (left < leftLimit && right < rightLimit) { if (sorted[left] <= sorted[right]) { buffer[i++] = sorted[left++]; } else { buffer[i++] = sorted[right++]; } } while (left < leftLimit) { buffer[i++] = sorted[left++]; } while (right < rightLimit) { buffer[i++] = sorted[right++]; } } var temp = sorted, sorted = buffer, buffer = temp; } return sorted; } function print(s) { document.write(s + '<br />'); } var data = [1, 4, 10, 2, 9, 3]; print('input: ' + data.join(', ')); print('output: ' + mergeSort(data).join(', '));