algoritmos divide y venceras

[m@o_614]

Saludos

Estoy estudiando algunos metodos de ordenamiento como Merge-Sort, Quick Sort y el metodo de busqueda binaria, y me he fijado que todos estos algoritmos utilizan la tecnica de dividir vectores en subvectores e irlos ordenando pero me fije que antes  de dividir el vector en 2 hace una suma, la de la variable ini mas el tamanio del vector

ini=1,sup=n;
i= (ini+sup)/2;

y me pregunto si esto es necesario, no seria mas logico dividir el tamanio del vector sobre 2 sin necesidad de hacer la dichosa suma??? de que me sirve la variable ini??

sup=n;
i= (sup/2);

de antemano gracias

[ecfisa]

Hola m@o_614.

no seria mas logico dividir el tamanio del vector sobre 2 sin necesidad de hacer la dichosa suma???

Definitivamente creo que no.

Pongamos como ejemplo la búsqueda dicotómica:

Código (cpp) [Seleccionar] Expandir


...
#define ELEM_NOT_FOUND -1

int binaria(int buscado, int *arreglo, int fin)
{
  int inicio = 0, medio;
  --fin;
  while(inicio <= fin) {
    medio = (inicio + fin) >> 1;
    if (buscado == arreglo[medio]) return medio;
    if (buscado < arreglo[medio])
      fin = medio - 1;       // la lista se redujo a: 0 - medio-1
    else
      inicio = medio + 1;    // la lista se redujo a: medio+1 - fin
  }
  return ELEM_NOT_FOUND;
}
...


En cada cliclo si el número buscado es mayor que el ubicado en el medio de la lista de elementos, se elimina la mitad inferior de esta, de lo contrario la superior. Y así se sigue reduciendo la lista de elementos a la mitad hasta que se encuentra el elemento o no haya mas elementos que buscar.
Esto no sucedería si siempre tomáramos como cotas a 0 y la cantidad total de elementos.

de que me sirve la variable ini??

Las variables inicio y fin van variando sus valores acorde a los condicionales como muestra el código anterior y sirven para fijar los nuevos límites luego de reducir la lista de elementos a la mitad en cada ciclo.

Saludos

[rir3760]

Un comentario. Se recomienda evitar la sustitución de la división por el desplazamiento de bits como en este caso:

Código (c) [Seleccionar] Expandir

medio = (inicio + fin) >> 1;
Porque en el desplazamiento a la derecha de un entero con signo si el bit de relleno es cero o uno depende de la implementación. En el caso de enteros sin signo donde el bit de relleno esta garantizado (es cero) es mejor dejar ese tipo de mejoras al compilador.

Un saludo

[ecfisa]

Hola rir3770.

Aclarando la aclaración , tu comentario es muy cierto y se cumple en el caso de enteros con signo negativos.

En este caso, a menos que enviáramos argumentos negativos como límites de la lista, el menor valor que puede tomar "medio" es 0.

Sin embargo, coincido plenamente en que no debe ser la costumbre usar la división por desplazamiento de bits.

Saludos.