C++ insertion tri erreur

Question

Lorsque je compile, il donne une erreur de violation d'accès en lecture. D'autres posts de débordement de pile indiquent que cela est dû à une boucle infinie. J'ai aussi vu que la valeur va à un très grand nombre négatif. Ma conjecture est que c'est parce que la liste [-1], mais je ne sais pas comment le changer afin qu'il ne dépasse pas la liste [0].

Code tri par insertion

void insertion_sort(int list[], int length) { 

for (int i = 1; i < length; i++) { 
    for (int j = i; (j > 0) && (list[j] < list[j - 1]); j--) { 
      swap(list, list[j - 1], list[j]); 
    } 
} 

}

code de fonction Swap

void swap(int list[], int & src, int & dest){ 
    int temp = list[src]; 
    list[src] = list[dest]; 
    list[dest] = temp; 
} 

Answer 1

Vous utilisez les valeurs de votre sorte comme un index dans votre échange. Rester simple.

Cela fonctionne.

void insertion_sort(int list[], int length) { 

    for (int i = 1; i < length; i++) { 
     for (int j = i; (j > 0) && (list[j] < list[j - 1]); j--) { 
      std::swap(list[j - 1], list[j]); 
     } 
    } 
} 

int main() 
{ 

    int arr[ 100 ]; 
    for(size_t i= 0; i < 100; ++i) 
     arr[ i ]= std::rand(); 

    insertion_sort(arr, 100); 

    return 0; 
} 

Ajouté:

Comme cela ressemble à un exercice de classe. Ce que vous voulez remarquer est que std::swap n'a aucune idée que votre list existe. Tout ce qu'il veut savoir, c'est quelles valeurs vous voulez échanger. Donc, si vous ne pouvez pas utiliser la bibliothèque standard, écrivez votre swap comme la norme.

Answer 2

void insertion_sort(int list[], int length) { 

for (int i = 1; i < length; i++) { 
    j = i; 
    while(j > 0 && list[j - 1] > list[j]){ 
     swap(list, list[j], list[j-1]); 
     j--; 
    } 
} 

Ceci devrait fonctionner pour le tri le plus petit vers le plus grand. La boucle while fait le travail de vérifier si elle doit être permutée et vérifie les positions déjà "triées" dans le tableau si elle doit être permutée de nouveau.

Codage heureux.