Escribí un algoritmo de clasificación de burbujas que clasifica una matriz asignada dinámicamente mediante la comparación de cadenas.

Aquí está mi código:

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;
            }
        }
    }
}

Mi problema es bastante obvio, pero parece que no puedo encontrar la manera de resolverlo: el código a veces falla en la línea (de manera indefinida):

Employee temp_employee = employees[i+1]

Es bastante obvio porque si i es igual al final de la matriz, acceder a la memoria con i+1 da como resultado un comportamiento indefinido. Sin embargo, si detengo el ciclo for con noOfEmployees-1, esto no sucede, pero el primer elemento nunca se ordena (obviamente).

¿Cómo puedo implementar el ordenamiento de burbujas correctamente? Parece una tarea tan trivial. ¿Me estoy perdiendo de algo?

0
Balázs Vincze 21 oct. 2017 a las 16:52

3 respuestas

La mejor respuesta

La siguiente versión simplificada en C puro funciona 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;
}

Según lo solicite, la función de la variable swapped es indicar que después de un paso completo a través de la matriz no se produjo un intercambio, por lo que indica que la matriz ahora está ordenada.

1
Paul Ogilvie 21 oct. 2017 a las 14:14

Otra solución:

#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;
}
0
Ahmed Saleh 21 oct. 2017 a las 14:21

Puede usar un límite explícito en el bucle externo.

También debe dividir las cosas en funciones más pequeñas.

bool operator <(Employee const & lhs, Employee const & rhs) {
    return lhs.combined_name() < rhs.combined_name();
}

// a.k.a. std::swap
void swap(Employee & lhs, Employee & rhs) {
    Employee temp(static_cast<Employee&&>(lhs)); // a.k.a. std::move
    lhs = static_cast<Employee&&>(rhs);
    rhs = static_cast<Employee&&>(temp);
}

void bubble_sort_impl(Employee * begin, Employee * end) {
    for (; end != begin; --end) {
        for (Employee * it = begin; it+1 != end; ++it) {
            if (*(it+1) < *it) {
                swap(*it, *(it+1));
            }
        }
    }
}

// do we really need "bubble_" or "_address_book" in this name?
void AddressBook::bubble_sort_address_book() {
    bubble_sort_impl(employees, employees + noOfEmployees);
}
1
Caleth 25 jun. 2018 a las 11:29