Pourquoi mon code ne fonctionne pas? Insertion Tri

Question

La fonction du tri d'insertion ne fonctionne pas. L'erreur est: Une fonction prend trop de temps à s'exécuter. Peut-être avez-vous une erreur dans votre code?

// this function 
var insert = function(array, rightIndex, value) { 
    for(var j = rightIndex; 
     j >= 0 && array[j] > value; 
     j--) 
    { 
     array[j + 1] = array[j]; 
    } 
    array[j + 1] = value; 
}; 

var insertionSort = function(array) { 
    for(var i = 0; i < array.length ; i++) 
    { 
     insert(array,i,array[i+1]); 
    } 
}; 

var array = [22, 11, 99, 88, 9, 7, 42]; 
insertionSort(array); 
println("Array after sorting: " + array); 
Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]); 

Answer 1

var insert = function(array, rightIndex, value) { 
 
    for(var j = rightIndex; 
 
     j >= 0 && array[j] > value; 
 
     j--) 
 
    { 
 
     array[j + 1] = array[j]; 
 
    } 
 
    array[j + 1] = value; 
 
}; 
 

 
var insertionSort = function(array) { 
 
    for(var i = 0; i < array.length - 1 ; i++) 
 
    { 
 
     insert(array,i,array[i+1]); 
 
    } 
 
}; 
 

 
var array = [22, 11, 99, 88, 9, 7, 42]; 
 
insertionSort(array); 
 
console.log(array);

vous devez exécuter votre boucle 1 moins itération que vous appelez la fonction insert() avec i + 1;

Answer 2

Votre problème est sur le choix de la position de tableau comme [i+1] et [j+1]

changement

var insert = function(array, rightIndex, value) { 
    for(var j = rightIndex; 
     j >= 0 && array[j] > value; 
     j--) 
    { 
     array[j + 1] = array[j]; 
    } 
    array[j + 1] = value; 
}; 

dans

var insert = function(array, rightIndex, value) { 
    for(var j = rightIndex; 
      j > 0 && array[j-1] > value; 
      j--) 
     { 
      array[j] = array[j-1]; 
     } 
     array[j] = value; 
    }; 

et

insert(array, i, array[i+1]); 

dans

insert(array, i, array[i]); 

Answer 3

Essayez de passer par le tableau arrière dans la fonction InsertionSort:

var insertionSort = function(array) { 
    for (var i = array.length - 1; i >= 0; i--) { 
    insert(array,i,array[i+1]); 
    } 
};