insertion tri bizzare run time

Question

J'essaie de trier un vecteur en utilisant le tri d'insertion mais pour la plupart des valeurs, il ne se termine pas. Si la taille du vecteur est supérieure à 3, la boucle ne se terminera pas pendant une période prolongée, pas du tout, ou elle se terminera rapidement comme prévu jusqu'à des valeurs de 5 au hasard.

#include <iostream> 
#include <fstream> 
#include <cstdlib> 
#include <ctime> 
#include <vector> 

void PRINT(std::vector<int> &data); 


void insertion(std::vector<int> data, clock_t Time); 

int main() 
{ 
    clock_t Time; 
    int dataSize, maxval; 
    std::vector<int> data; 

    srand(time(0)); 


    std::cout<<"input vector size\n"; 
    std::cin>>dataSize; 
    std::cout<<"input max value\n"; 
    std::cin>>maxval; 

    Time=clock(); 
    for(int i=0; i<dataSize; i++) 
    { 
     data.push_back(1+rand()%maxval); 
    } 
    Time=clock()-Time; 
    std::cout<<"ticks to randomize "<<Time<<" seconds "<<float(Time)/CLOCKS_PER_SEC<<std::endl; 

    insertion(data, Time); 
    return 0; 
} 

void PRINT(std::vector<int> &data) 
{ 
    std::cout<<"data contains: "; 
    for(int i=0; i<data.size(); i++) 
    std::cout<<data[i]<<", "; 
    std::cout<<std::endl; 
} 


void insertion(std::vector<int> data, clock_t Time) 
{ 
    bool sorted;  
    std::vector<int>::iterator j; 

    Time=clock(); 
    for(int i=1; i<data.size(); i++) 
    { 
     j=(data.begin()+i-1); 
     sorted=false; 

     while(!(j==data.begin())&&!sorted) 
     { 
      if (*j<data[i]) 
      { 
       sorted=true; 
       data.insert((j+1),data.at(i)); 
      } 

      j--; 
     } 

    } 
    Time=clock()-Time; 

    std::cout<<"insertion:\nticks taken "<<Time<<"\n"; 
    std::cout<<"seconds "<<float(Time)/CLOCKS_PER_SEC<<std::endl; 
    PRINT(data); 
} 

Quelqu'un peut-il voir pourquoi mon implémentation a un temps d'exécution dément à des valeurs plus élevées? Y a-t-il une meilleure façon de mettre en œuvre cela?

Answer 1

Voici une erreur flagrante.

std::vector<int>::iterator j; 
//... 
for (int i = 1; i < data.size(); i++) 
{ 
    j = (data.begin() + i - 1); // iterator j points to a location in the vector 
    //... 
    while (!(j == data.begin()) && !sorted) 
    { 
     //... 
     data.insert((j + 1), data.at(i)); // vector being resized here 
    } 
    j--; // this iterator is now invalidated! 

Le problème est que vous changez la taille du vecteur dans le milieu de la boucle, et la j itérateur qui pointait à l'intérieur du vecteur est invalidée en raison du vecteur redimensionnée. Vous essayez de décrémenter l'itérateur invalide, et tout se sépare de là (l'exécution dans Visual Studio montre une boîte de message de débogage que l'itérateur est "non décrémentable"). Utilisez l'indexation droite en utilisant un nombre entier (pas un itérateur), ou la technique montrée sur le lien dans mon commentaire sur la mise en œuvre du tri d'insertion.