Combinar arreglos ordenados en C++

Question

Necesito combinar los elementos de dos arreglos de manera intercalada y ordenarlo durante su inserción. Sin embargo, algo extraño pasa cuando ordeno el segundo arreglo (arreglo2), ya que me modifica el primer elemento del primer arreglo (arreglo1) y no tengo idea por qué.

Estoy compilando en Zinjai y lo he probado en CodeBlocks, pero el problema sigue igual:

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

#define EXT 5

void ordenar (int *array);
void generar (int *a);

void ordenar(int *array){
    int aux=0;

    for(int j= 0 ; j<EXT ; j++){
        for(int i=0 ; i<EXT-j; i++){
            if(array[i] > array[i+1]){
                aux = array[i];
                array[i] = array[i+1];
                array[i+1] = aux;
            }
        }
    }

    cout << "Arreglo ordenado:";
    for(int k=0 ; k<EXT; k++)
        cout << "\t" << array[k];
    cout<<endl;
}

void generar (int *a) {

    cout << "Arreglo generado:"; 
    for(int i=0 ; i<EXT ; i++){
        a[i] = rand()%10;
        cout << "\t" << a[i];   
    }

    cout << "\n";
}

int main(int argc, char *argv[]) {

    int arreglo1[EXT];
    int arreglo2[EXT];
    int arregloS[EXT*2];
    int a = 0, b = 0, c = 0;

    srand(time(NULL));

    generar(arreglo1);
    ordenar(arreglo1);

    cout << "\n\n";

    generar(arreglo2);
    ordenar(arreglo2);
    cout << "\n\n";

    do{
        if (arreglo2[a] <= arreglo1[b]) {
            arregloS[c] = arreglo2[a];
            a++;
        }
        else if (arreglo2[a] >= arreglo1[b]) { 
            arregloS[c] = arreglo1[b];
            b++;
        }
        c++;
    }while(c < EXT*2);

    cout << "Arreglo final:"; 
    for (int i = 0 ; i<2*EXT ; i++){
        cout << "\t" << arregloS[i];
    }
    cout << endl; 

    return 0;
}

eferion · Answer 1 · 2018-09-27T08:25:36.487

En este bucle:

for(int j= 0 ; j<EXT ; j++){
    for(int i=0 ; i<EXT-j; i++){
        if(array[i] > array[i+1]){
            aux = array[i];
            array[i] = array[i+1];
            array[i+1] = aux;
        }
    }
}

Si j==0, i podrá alcanzar el valor i=EXT-1, con lo que tendrás la siguiente secuencia:

aux = array[EXT-1];
array[EXT-1] = array[EXT];
array[EXT] = aux;

Es decir, estarás accediendo a elementos que no pertenecen al array. Recordemos que los índices empiezan en cero, luego el índice EXT no es válido.

La función de ordenación debería parecerse más bien al siguiente ejemplo:

for( int i=0; i<EXT-1; i++ )
{
  for( int j=i+1; j<EXT; j++ )
  {
    if( array[i] > array[j] )
    {
      int aux = array[i];
      array[i] = array[j];
      array[j] = aux;
    }
  }
}

O, haciendo uso de funciones de la librería estándar:

for( int i=0; i<EXT-1; i++ )
{
  for( int j=i+1; j<EXT; j++ )
  {
    if( array[i] > array[j] )
      std::swap(array[i],array[j]);
  }
}

Por otro lado tu función para fusionar los arrays no es correcta y el motivo es que no verifica si cualquiera de los dos arrays ya ha sido copiado completamente (es decir, si a==EXT o b==EXT). En consecuiencia la fusión acabará accediendo a elementos que no pertenecen a los arrays y, debido a ello, mostrar resultados erróneos.

Una posible solución:

for( int a = 0, b = 0, c = 0; c < EXT*2; c++ )
{
  if( a == EXT )
  {
    arregloS[c] = arreglo2[b];
    b++;
  }
  else if( b == EXT || arreglo1[a] <= arreglo2[b] )
  {
    arregloS[c] = arreglo1[a];
    a++;
  }
  else
  {
    arregloS[c] = arreglo2[b];
    b++;
  }
}

Lo primero que hacemos es verificar que a y b son índices válidos. Piensa que si un índice no es valido se implica que el otro tiene que serlo obligatoriamente. Es facil verificar que si a==EXT y b==EXT entonces, c = a+b = EXT+EXT = 2 * EXT, que es justamente el rango en el que se mueve c.

score 1 · Answer 2 · edited Jun 11 '20 at 10:54

He compilado y probado tu código y funciona correctamente, no observo el comportamiento "Cuando ordeno arreglo2 me modifica el primer elemento dearreglo1", tal vez si compartes los datos de entrada, los datos de salida y los datos que esperabas obtener podamos encontrarlo.

Mientras tanto, etiquetaste la pregunta como C y C++ pero tu código es completamente incompatible con C (de ahí la eliminación de dicha etiqueta); dado que tu código es C deberías tener en cuenta lo siguiente:

Las cabeceras <stdlib.h> y <time.h> son de c no de c++. Estas cabeceras disponen de una versión adaptada a C++ que tiene el prefijo c y carece de extensión. Si realmente necesitas usar las cabeceras de C (que nunca será el caso) debes usar los equivalentes de C++ <cstdlib> y <ctime> . Lee este hilo para saber por qué.
No hay obligación de usar la cláusula using namespace std; pues es sólo es una ayuda a la escritura de código; si decides usar esta cláusula no lo hagas en el ámbito global, úsala en el ámbito más pequeño posible. Lee este hilo para saber por qué.
La función rand() pertenece a las librerías de C, se desaconseja usarla en C++ pues puede no ser portable y puede ofrecer resultados y rendimiento cuestionables, por ello se está estudiando deprecarla . A partir del estándar C++11 existe una completa librería de generación de números pseudoaleatorios que deberías usar en su lugar. Lee este hilo para saber por qué.
Evita usar macros (#define), usa en su lugar constantes. Las macros son una utilidad de preprocesador no del lenguaje, por ello ignoran los contextos y espacios de nombres, pueden causar problemas de compilación, no pertenecen al sistema de tipos y son propensas a ser usadas de maneras problemáticas.
Evita usar punteros en crudo; para almacenar valores usa formaciones¹ si el tamaño es conocido en tiempo de compilación o contenedores si el tamaño es dinámico. Evita abusar de std::endl (pues puede causar problemas de rendimiento) y favorece el uso del salto de línea explícito (\n). Lee este hilo para saber por qué.
Deja a tus variables respirar, en los 90 teníamos pantallas de 80 caracteres de ancho y 25 líneas de alto, por entonces tenía sentido apretujar el código para que cupiera en la pantalla. Hoy día tenemos pantallas enormes y separar las variables y operadores hace que el código sea más legible.
No reinventes la rueda, si tienes que hacer un ejercicio de ordenación está bien que redactes el código de ordenar, pero por lo demás usa las herramientas que el lenguaje ya te proporciona, te hará la vida más fácil y tu código será más conciso y claro.
Favorece el pre-incremento frente al post-incremento.

Teniendo en cuenta todo esto, tu código podría quedar así:

Propuesta:

#include <iostream>
#include <random>
#include <algorithm>

constexpr int EXT = 5;

void ordenar(int (&array)[EXT]){
//               ~~~~~~~ <--- Formación recibida como referencia, no como puntero en crudo.
    int aux = 0;

    for (int j = 0 ; j < EXT; ++j){
        for (int i = 0; i < EXT - j; ++i){
            if(array[i] > array[i + 1]){
                std::swap(array[i], array[i + 1]);
            }
        }
    }

    std::cout << "Arreglo ordenado:";
    for (const auto &k : array) { // bucle for de rango
        std::cout << '\t' << k;
    }

    std::cout << '\n';
}

void generar(int (&a)[EXT]) {
//               ~~~~ <--- Formación recibida como referencia, no como puntero en crudo.

    // Generador de números entre 0 y 9 uniformemente distribuidos
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, 9);
    // Generamos números
    std::generate(std::begin(a), std::end(a), [&]() { return dis(gen); });

    std::cout << "Arreglo generado:"; 
    for (const auto &i : a) { // bucle for de rango
        std::cout << '\t' << i;
    }

    std::cout << '\n';
}

int main() {

    using namespace std;

    int arreglo1[EXT];
    int arreglo2[EXT];
    int arregloS[EXT*2];
    int a = 0, b = 0, c = 0;

    generar(arreglo1);
    ordenar(arreglo1);

    cout << "\n\n";

    generar(arreglo2);
    ordenar(arreglo2);
    cout << "\n\n";

    do {
        if (arreglo2[a] <= arreglo1[b]) {
            arregloS[c] = arreglo2[a];
            ++a;
        }
        else if (arreglo2[a] >= arreglo1[b]) { 
            arregloS[c] = arreglo1[b];
            ++b;
        }
        ++c;
    } while (c < EXT * 2);

    cout << "Arreglo final:"; 
    for (int i = 0 ; i<2*EXT ; i++){
        cout << "\t" << arregloS[i];
    }
    cout << endl; 

    return 0;
}

También conocidas como arreglos o en inglés arrays.

... y los errores que tu ves y los demás no. Tus respuestas siempre aportan algo — eferion, Sep 27 '18 at 08:26

score 0 · Answer 3 · answered Sep 27 '18 at 07:48

0

En la función ordenar, en la linea.

                array[i+1] = aux;

El valor de la variable i llega a 4, que sumando a 1 desborda el arreglo.

answered Sep 27 '18 at 07:48

logann

1

Bienvenido a [es.so]. Aparte de comentar el error, que es algo que se agradece, estaría bien que incluyeses alguna posible solución al problema. Así la respuesta estaría completa y podrías empezar a recibir positivos. – eferion Sep 27 '18 at 12:50

Combinar arreglos ordenados en C++

3 Answers3

Propuesta: