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