Этот простой код mergeSort дает неправильный ответ. Может кто-нибудь найти ошибку? - PullRequest
Новая
       5

Этот простой код mergeSort дает неправильный ответ. Может кто-нибудь найти ошибку?

0 голосов
/ 09 мая 2018

Кажется, проблема в том, что mergeSort разбивает [300,200, 100] на [300,200] и [100]. Затем он успешно сливается и сортирует [300,200] в [200,300]. Проблема возникает сейчас: вместо слияния [200,300] с [100], алгоритм запускает процедуру сортировки между [300] и [100]. У меня есть подозрение, что проблема из-за закрытия Javascript, из-за которого значение j интерпретируется по-разному в какой-то момент. Кто-нибудь может мне помочь? 

function mergeSort(A,start,end){
    console.log("Sorting " + A + " between " + start + " and " + end)
    if (start==end){
        console.log("Reached singleton element: " + A[start])
        return;
    } 

    j = Math.floor((end+start)/2);

    mergeSort(A,start,j);
    console.log("Sorted " + A + " between " + start + " and " + j + ". Now sorting between " + (j+1) + " and " + end)
    mergeSort(A,(j+1),end);
    merge(A,start,(j+1),end);
    return A
}  

function merge(A,s,p,e){ 
    var i = s;
    var j = p;
    var finalArray = [];
    while(i < p && j < e+1){
        if (A[i] <= A[j]){
            finalArray[i+j-s-p] = A[i];
            i++
        } 
        else if (A[j] < A[i]){
               finalArray[i+j-s-p] = A[j];
               j++
        }  
    }

    if (i == p){
        while (j < e+1 ){
            finalArray[i-s+j-p] = A[j];
            j++
        }
    }

    if (j == e+1){
        while (i < p ){
            finalArray[i-s +j-p] = A[i];
            i++ 
       }    
    }

    for(var q = s; q <e+1;q++){
        A[q] = finalArray[q-s]
    }
}



A = [300,200, 100] // Gives [ 200, 100, 300 ]
mergeSort(A, 0, (A.length-1));

1 Ответ

0 голосов
/ 09 мая 2018

Это вопрос объема.Изменение объявления j исправляет это: 

let j = Math.floor((end+start)/2);

Я реорганизовал функцию слияния.Единственная причина, по которой я не переименовал переменные, в том, что я на мобильном телефоне.Кто-то с большим знанием JS, вероятно, имеет больше улучшений: 

function merge(A,s,p,e) { 
    let i = s;
    let j = p;
    let finalArray = [];
    while(i < p && j <= e) {
        if (A[i] <= A[j]) {
            finalArray.push(A[i])
            i++
        } 
        else {
            finalArray.push(A[j])
            j++
        }  
    }

    while (j <= e) {
        finalArray.push(A[j]);
        j++
    }

    while (i < p) {
        finalArray.push(A[i]);
        i++  
    }

    for(let q = s; q <= e; q++) {
        A[q] = finalArray[q-s]
    }
}
...