Mi codigo de ordenacion por insercion no funciona bien

[aguml]

Hola amigos, estoy intentando crearme un pequeño codigo el cual coja dos arrays con enteros y los vaya insertando ordenados en un tercer array de forma ya ordenada sin tener que usar ningun otro metodo de ordenacion en ninguno de los 3 arrays. El caso es que no doy con la tecla y hace cosas raras. Os pongo mi codigo a ver si pueden echarme una mano:

Código PHP:

#include <stdio.h>
#include <stdlib.h>
 
int buscarPos(int valor, int array[], int size_array)
{
    int pos=0,aux_pos;
 
    do{
        aux_pos=pos;
        if(valor > array[pos]){
            pos = (pos + size_array) / 2;
            if(aux_pos==pos && pos > 0){
                pos++;
            }
        }else{
            if(pos > 0 && array[pos-1] < valor){
                break;
            }else if(size_array > 0 && valor <= array[pos])
                break;
            size_array = size_array - aux_pos;
            pos = size_array / 2;
            if(aux_pos==pos && pos > 0){
                pos--;
            }
        }
    }while(pos < size_array && aux_pos != pos);
    return pos;
}
 
int insertarElemento(int valor, int array[], int size_array, int pos)
{
    int i;
 
    for (i=size_array; i > pos; i--) {
        array[i]=array[i-1];
    }
    array[pos]=valor;
 
    size_array++;
    return size_array;
}
 
int main(int argc, char* argv[])
{
    int a[]={50,2,2,100,5,3,1,7,9};
    int b[]={4,2,6,10,8};
    //int *c;
    int c[50];
    int pos,i,j;
    int nElements=0,size_array1,size_array2;
 
    //Solicito la memoria necesaria para colocar la lista combinada ordenada
    //c= calloc((sizeof(a)+sizeof(b))/sizeof(int),sizeof(int));
    size_array1=sizeof(a)/sizeof(int);
    size_array2=sizeof(b)/sizeof(int);
 
    for(i=0,j=0;nElements < size_array1+size_array2;){
        if(i<size_array1){
            //Obtengo la posicion que tomará dicho elemento en la lista en orden ascendente
            pos = buscarPos(a[i],c,nElements);
            nElements = insertarElemento(a[i],c,nElements,pos);
            i++;
        }
        if(j<size_array2){
            pos = buscarPos(b[j],c,nElements);
            nElements = insertarElemento(b[j],c,nElements,pos);
            j++;
        }
    }
 
    for(pos=0;pos<nElements;pos++)
        printf("%i\n",c[pos]);
    //free(c);
    getchar();
    return 0;
} 


Gracias por adelantado.

[ecfisa]

Hola.

Revisa este modo:

Código PHP:

#include <stdio.h>
#include <stdlib.h>

void insertSort(int *, int);

int main()
{
  int a[] = { 50,2,2,100,5,3,1,7,9 };
  int b[] = { 4,2,6,10,8 };
  int i;
  int asz = sizeof( a ) / sizeof( a[0] );
  int bsz = sizeof( b ) / sizeof( b[0] );

  // pasar: a y b -> c
  int *c = ( int* ) malloc( sizeof(int) * ( asz + bsz ) );

  for ( i = 0; i < asz; i++ ) c[i] = a[i];
  for ( i = 0; i < bsz; i++ ) c[asz+i] = b[i];

  // mostrar original
  for ( i = 0; i < asz + bsz; i++ ) printf( "%d ",c[i] ); printf( "\n\n" );

  // ordenar
  insertSort(c, (asz+bsz) );

  // mostrar ordenado
  for ( i = 0; i < asz + bsz; i++ ) printf( "%d ",c[i] );

  free( c );

  getchar();
  return 0;
}

// ordenamiento por inserción
void insertSort( int *array, int size )
{
  int i,j, tmp;

  for( i = 1; i < size; ++i ) {
    tmp = array[i];
    j = i;
    while ( j > 0 && tmp < array[j - 1] ) {
      array[j] = array[j - 1];
      j--;
    }
    array[j] = tmp;
  }
} 


Salida:


Saludos

[aguml]

Ese método ya lo estuve viendo pero no puedo usarlo porque ahí tu metes todos los elementos dentro y luego los ordenas y yo quiero ir metiendo los de uno en uno y a la vez colocando ya ordenado.

[ecfisa]

Hola.

Entiendo... no deseas ordenar un arreglo por el método de inserción, sino ir insertando en órden los ítems a medida que se van agregando al arreglo.

Entonces podes tratarlo así:

Código PHP:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void insertInOrder( int *, int, int );

int main( )
{
  int a[] = { 50,2,2,100,5,3,1,7,9 };
  int b[] = { 4,2,6,10,8 };
  int i;
  int asz = sizeof( a ) / sizeof( a[0] );
  int bsz = sizeof( b ) / sizeof( b[0] );
  int tot = asz + bsz;

  // inicializar c
  int *c = ( int* ) malloc( sizeof(int) * tot );
  for ( i = 0; i < tot; i++ ) c[i] = INT_MAX;
  
  // insertar elementos de a en c
  for ( i = 0; i < asz; i++ ) insertInOrder( c, tot, a[i] );
  // insertar elementos de b en c
  for ( i = 0; i < bsz; i++ ) insertInOrder( c, tot, b[i] );
  
  // mostrar
  for ( i = 0; i < tot; i++ ) printf( "%d ", c[i] );

  free( c );
  getchar();

  return 0;
}

// Insertar en órden
void insertInOrder(int *array, int size, int value)
{
  int i = size - 1;
  while( value < array[i] && i >= 0 ) {
    array[i+1] = array[i];
    i--;
  }
  array[i+1] = value;
} 


Salida:


Saludos

[aguml]

Sí, eso ya lo hice y funciona pero la idea era hacerlo de otra forma como sigue. Imagina un arreglo con 1 millón de elementos a insertar en orden, con tu método tienes que leer todo cada vez hasta encontrar su posición y eso cuantos más elementos más tardará.
Mi idea es esta
Si tengo ya los elementos:
1,2,5,6,7,10,15,20
Quiero insertar 9.
La posición inicial será la última con lo que en primer lugar lo comparo con el 20.
Como es menor divido el índice entre 2 para comparar con el del medio que en este caso sería el 6.
Como 9 es mayor que 6 la idea es coger el rango entre la posición actual y la última y comparar con el del centro. En este caso sería con el valor 10 y como 9 es menor coger el rango entre el valor 6 y el 10 y divido entre 2 y esta vez comparará con el 7 y como es mayor cojo el rango de los valores del 7 al 10 y lo divido entre 2 y ya obtendría la posición correcta.
Parece un lio pero pienso que cuando se trabaje con arrais muy grandes puede mejorar los tiempos con respecto a lo que indicas pero no doy con la tecla. He estado dándole muchas vueltas y ahora mismo la tengo así la función que obtiene la posicion pero no funciona a como quiero:

Código PHP:

int buscarPos(int valor, int array[], int size_array) 
{ 
    int pos=size_array,aux_pos; 
    if (size_array > 0){
        do{ 
            aux_pos=pos; 
            if (valor > array[pos-1]){
                if (aux_pos == pos || valor < array[pos]){ 
                    break;
                }else {
                    pos = size_array - (size_array -pos)/2;
                }
            }else if (valor < array [pos-1]){
                size_array = pos;
                pos = size_array / 2;
                if(aux_pos==pos){
                    break;
                }
            }else {
                break;
            }
        }while(aux_pos != pos); 
    }
    return pos; 
} 


[ecfisa]

Hola.

Si buscas velocidad de ordenamiento sobre un arreglo, por sencillez, pensaría en el algorítmo QuickSort.

Usando inserción, por mas que optimices la búsqueda del índice donde el elemento deberá ser insertado, no podrás evitar tener que hacer : N - posición desplazamientos. Imagina que en algún punto ya existen 1000000 elementos ordenados en el arreglo, vg:

[1,3,3,4,5,6,6,7,7, ... ,979827,992799,993256]

Entonces aparece el número 2... la búsqueda determina que corresponde insertar el próximo elemento en la segunda posición del arreglo. ¡ Ahora tendrá que efectuar 1000000-2 desplazamientos para hacerle lugar !
Y dado que desplazar posiciones de memoria es una taréa bastante lenta, no veo al método como el candidato mas veloz.

Otras opciones que te podrían resultar interesantes:

• HeapSort
• Árbol binario de búsqueda

Por último, si no necesitas tener los datos físicamente ordenados, podría servirte: Tabla hash

Saludos

[aguml]

Lo siento pero no pude contestar antes porque no he estado con internet hasta ahora. Al final lo he conseguido asi:

Código PHP:

#include <stdio.h>
#include <stdlib.h>

#define NARRAYS 4

int buscarPos(int valor, int array[], int nElementos);
int insertarElemento(int valor, int array[], int nElementos, int pos);
int obtenerIndice(int index, int valIni, int valFin);

int main(int argc, char* argv[])
{
    //Esta es usada como contador para los bucles FOR
    int i;

    //Estas son los arrays que queremos pasar ordenados a un solo array
    //Tiene que ser intercalandolos, o sea primero uno del a, luego uno del b,
    //luego otro del c...
    int a[]={50,2,11,55,3,1,7,9};
    int b[]={4,2,6,10,8};
    int c[]={9,8,7,15};
    int d[]={56,44,22,33,88,66,77,99};

    //Puntero para el array dinamico que contendrá todos los elementos ordenados
    int *ordenados;

    //Usada para guardar en el la posicion en la que hay que insertar el elemento
    int pos;

    //Contador del numero de elementos insertados
    int nElements=0;

    //Esta variable es necesaria para saber a que array le tocará insertar
    int balanceo=0;

    //Arrays usados para almacenar los valores o punteros a las variables
    //necesarias para el balanceo entre los arrays
    int contador[NARRAYS],*parray[NARRAYS],size[NARRAYS],sizeTotal=0;

    //Las inicializo con los valores y direcciones iniciales
    parray[0]=a;
    parray[1]=b;
    parray[2]=c;
    parray[3]=d;

    size[0]=sizeof(a)/sizeof(int);
    size[1]=sizeof(b)/sizeof(int);
    size[2]=sizeof(c)/sizeof(int);
    size[3]=sizeof(d)/sizeof(int);

    //Obtengo el total de elementos que debe contener el array dinamico
    for(i=0; i<NARRAYS; sizeTotal += size[i++]);

    //Inicializo los contadores
    for(i=0; i<NARRAYS; contador[i++]=0);

    //Solicito la memoria necesaria para colocar la lista combinada ordenada
    ordenados = calloc(sizeTotal ,sizeof(int));

    while(nElements < sizeTotal){
        if(contador[balanceo] < size[balanceo]){
            //Obtengo la posicion que tomará dicho elemento en la lista en orden ascendente
            pos = buscarPos(parray[balanceo][contador[balanceo]],ordenados,nElements);
            //Inserto el elemento en dicha posicion
            nElements = insertarElemento(parray[balanceo][contador[balanceo]],ordenados,nElements,pos);
            contador[balanceo]++;
        }
        balanceo=obtenerIndice(balanceo,0,3);
    }

    for(pos=0;pos<nElements;pos++)
        printf("%i\n",ordenados[pos]);
    free(ordenados);
    getchar();
    return 0;
}
//---------------------------------------------------------------------------

int buscarPos(int valor, int array[], int nElementos)
{
    //Esta la uso como indice para posicionarme en el elemento del array
    //Empiezo comparando con el ultimo elemento por lo que lo inicializo para ello
    int pos=nElementos-1;


    int aux_pos; //La uso para saber si al dividir me da el mismo indice
    int pos_ini=0; //Contendra el indice inicial desde el que buscar
    int pos_fin=pos; //Contendra el indice final hasta donde buscar

    //En este condicional solo entro si el numero de elementos es mayor que 0
    //ya que si vale 0 solo tengo que colocarlo en la primera posicion
    if(nElementos > 0)
    {
        do{
            aux_pos=pos;
            if(valor > array[pos]){
                //Si entro aqui quiere decir que todos los elementos del array
                //hasta la posicion indicada en el indice son menores con lo que
                //la posicion inicial pasa a ser la posicion indicada por pos
                pos_ini = pos;

                //Obtengo el indice del centro entre la posicion inicial y la final
                pos = pos_ini + (pos_fin - pos_ini) / 2;

                //Si el valor es mayor que el de la posicion del array y se
                //cumple el siguiente condicional hay que incrementar en 1 la
                //posicion ya que solo hay que pasar esa posicion para que quede
                //en el sitio correcto
                if(aux_pos == pos){
                    pos++;
                    break;
                }
            }else if(valor < array[pos]){
                //Si entro aqui es porque todos los elementos del array desde la
                //posicion indicada hasta el final del array son mayores que el
                //valor buscado con lo que la posicion final pasa a ser la
                //posicion indicada por pos
                pos_fin = pos;

                //Obtengo el indice del centro entre la posicion inicial y la final
                pos = pos_ini + (pos_fin - pos_ini) / 2;
            }
        }while(aux_pos != pos);
    }else{
        pos=0;
    }
    return pos;
}
//---------------------------------------------------------------------------

int insertarElemento(int valor, int array[], int nElementos, int pos)
{
    int i;

    //Si hay que intercalar un elemento desplazo todos los que esten a partir de
    //esa posicion hacia el siguiente elemento a la derecha
    for (i=nElementos; i > pos; i--) {
        array[i]=array[i-1];
    }
    //Coloco el elemento en el lugar que le corresponde
    array[pos]=valor;

    nElementos++;
    return nElementos;
}
//---------------------------------------------------------------------------

//Obtengo el indice usando el balanceo deseado en este caso
int obtenerIndice(int index, int valIni, int valFin)
{
    index++;
    if(index > valFin)
        index=valIni;
    return index;
}
//--------------------------------------------------------------------------- 


Realmente no es algo estrictamente de eficiencia sino que estaba experimentando a ver si podia hacerlo o era muy complejo para mi y digamos que esta a medio camino jajaja.
Tengo algunas dudas:
1-Esta parte:

Código PHP:

    //Las inicializo con los valores y direcciones iniciales
    parray[0]=a;
    parray[1]=b;
    parray[2]=c;
    parray[3]=d; 


¿Hay alguna manera de inicializarlo usando un bucle de forma sencilla como hago por ejemplo con los contadores?
2-Misma duda pero con esta parte:

Código PHP:

    size[0]=sizeof(a)/sizeof(int);
    size[1]=sizeof(b)/sizeof(int);
    size[2]=sizeof(c)/sizeof(int);
    size[3]=sizeof(d)/sizeof(int); 


La cosa es que si añado mas arrays se me puede olvidar inicializar uno de estos dos para ese array por eso pregunto si hay alguna manera de desentenderme de ello haciendo que se inicialicen todos en un bucle.
Si todos los arrays no fueran cada uno por su lado, fueran todos en un array de arrays y todos con el mismo tamaño no habria problema pero quiero saber como hacerlo en este caso en que cada array va por su lado y pueden tener tamaños diferentes.

[aguml]

Por otro lado con 2 arrays de 1000000 bastaria con unas 20 iteraciones maximo por numero en el peor de los casos ya que truncando los decimales como hago tengo esto:

1000000/2=500000; 500000/2=250000; 250000/2=125000; 125000/2=75000; 75000/2=37500; 37500/2=18750; 18750/2=9375; 9375/2=4687; 4687/2=2343; 2343/2=1171; 1171/2=585; 585/2=292; 292/2=146; 146/2=73; 73/2=36; 36/2=18; 18/2=9; 9/2=4; 4/2=2; 2/2=1; 1/2=0

[mamcx]

Para este tipo de tareas es bueno este recurso:

https://rosettacode.org/wiki/Categor...ing_Algorithms

(Cada ejemplo esta implementado en decenas de diferentes lenguajes, no solo mostrando como seria en el tuyo sino dejandote ver otras formas de hacerlo!)

Y si estas buscando como hacer el sort mas eficiente, tienes que leer los diversos algoritmos a ver cual da la talla para el caso especifico:

https://stackoverflow.com/questions/...ly-sorted-data