C++ Bubble sort tableau dynamiquement alloué

Question

Je commence tout juste à commencer avec C++ et la gestion de la mémoire, alors s'il vous plaît nu avec moi!

J'ai écrit un algorithme de tri à bulles qui trie un tableau alloué dynamiquement en utilisant la comparaison de chaînes.

Voici mon code:

void AddressBook::bubble_sort_address_book(){ 
    bool swapped = true; 
    while(swapped){ 
     swapped = false; 
     for(int i = 0; i < noOfEmployees; i++){ 
      if(employees[i].combined_name() > employees[i+1].combined_name()){ 
       Employee temp_employee = employees[i+1]; 
       employees[i+1] = employees[i]; 
       employees[i] = temp_employee; 
      } 
     } 
    } 
} 

Mon problème est assez évident, mais je ne peux pas sembler comprendre comment le résoudre: Le code échoue parfois sur la ligne (de manière non définie):

Employee temp_employee = employees[i+1] 

Son assez évident parce que si i est égal à la fin du tableau, l'accès à la mémoire avec i+1 résultats dans un comportement non défini. Cependant, si j'arrête la boucle for avec noOfEmployees-1, cela ne se produit pas mais le premier élément n'est jamais trié (évidemment).

Comment puis-je implémenter le tri à bulles correctement? Cela semble être une tâche si triviale. Est-ce que je manque quelque chose?

Merci!

Answer 1

La version simplifiée suivante dans le plus pur C fonctionne très bien:

int employees[10]= {3,1,7,6,9,7,1,0,2,6}; 
int noOfEmployees= 10; 

void bubble_sort_address_book(void){ 
    bool swapped = true; 
    int i; 
    while(swapped){ 
     swapped = false; 
     for(i = 0; i < noOfEmployees-1; i++){ 
      if(employees[i] > employees[i+1]){ 
       int temp_employee = employees[i+1]; 
       employees[i+1] = employees[i]; 
       employees[i] = temp_employee; 
       swapped= true; 
      } 
     } 
    } 
} 
int main() 
{ 
    int i; 
    bubble_sort_address_book(); 
    for (i=0; i<noOfEmployees; i++) { 
     printf("emp %d= %d\n", i, employees[i]); 
    } 
    return 0; 
} 

Comme vous le demandez, la fonction de la variable swapped est d'indiquer que la suite d'un passage complet à travers le réseau sans échange a eu lieu et il indique le tableau est maintenant trié.

Answer 2

une autre solution:

#include <iostream> 
#include <vector> 


using namespace std; 

int employees[10] = { 3,1,7,6,9,7,1,0,2,6 }; 


void bubble_sort_address_book(void) { 
    bool swapped = true; 
    int i; 
    int noOfEmployees = 10; 
    while (swapped) { 
     swapped = false; 
     for (i = 1; i <= noOfEmployees ; i++) { 
      if (employees[i] > employees[i - 1]) { 
       int temp_employee = employees[i - 1]; 
       employees[i - 1] = employees[i]; 
       employees[i] = temp_employee; 
       swapped = true; 
      } 
     } 
    } 
} 
int main() 
{ 
    int i; 
    int noOfEmployees = 10; 
    bubble_sort_address_book(); 
    for (i = 0; i<noOfEmployees; i++) { 
     printf("emp %d= %d\n", i, employees[i]); 
    } 
    return 0; 
}