Título: algoritmos divide y venceras Publicado por: m@o_614 en 14 Septiembre 2013, 02:46 am 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 Título: Re: algoritmos divide y venceras Publicado por: ecfisa en 14 Septiembre 2013, 07:56 am Hola m@o_614.
Citar 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
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. Citar 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 :) Título: Re: algoritmos divide y venceras Publicado por: rir3760 en 16 Septiembre 2013, 19:43 pm Un comentario. Se recomienda evitar la sustitución de la división por el desplazamiento de bits como en este caso:
Código 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 Título: Re: algoritmos divide y venceras Publicado por: ecfisa en 16 Septiembre 2013, 21:29 pm 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. :) |