Dec
27

Ordenamiento Rápido (Quicksort)

El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida. Fue desarrollada por C. Antony R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
El algoritmo fundamental es el siguiente:
  • Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
  • Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
  • La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
  • Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
  • En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
  • En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de 0(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas.
  • En el caso promedio, el orden es O(n·log n).
No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote. more...
Dec
17

Mexicanadas con php

Function dies($msg){
		Echo utf8_encode(ob_get_clean());
		Die(utf8_encode($msg))
	}
Sólamente por estas cosas detesto ser Méxicano :P, y… creo que se pega, así que, ¡Aguas! :D
Dec
12

Hoy examen de Ensamblador

Así es, hoy es el día de mi desceso... ¡¡Examen de ensamblador!! y,... Seguramente, reprobaré :-(. No me sirvio de nada la documentación, ni los ejemplos, en especial los últimos que ni se que hacen jeje ¡¡ Pase con 8 :D ;-) !!

  • Programa que ejemplifica el uso básico de los procedimientos (No macros) - Aplicación que utiliza procedimientos (No macros) y ejemplifica correctamente la forma en que se debe mandar llamar un procedimiento con y sin parámetros además de como declarar su prototipo. La aplicación tiene procedimientos con nombres bastante explicitos y literales en su comportamiento.
  • Limpia pantalla y cambia el color del fondo - Limpia pantalla y cambia color del fondo conforme se va escribiendo.
  • Simulación de un menu de opciones - Aplicación que simula el comportamiento de un menu de opciones, ya que cambia los atributos a la línea seleccionada dando el efecto de \"línea seleccionada\". Funciona con las teclas 8 y 2 para bajar y subir.
  • gotoxy, leer y write con procedimientos (No macros) - Creación de los procecimientos gotoxy, leer caracter y write utilizando procedimientos (no macros)
  • Lee dos cadenas y las compara - Lee dos cadenas y las compara
  • movs.asm - Aplicación que utiliza movs para moder cadenas.
  • scas.asm - Programa que lee una cadena y busca un caracter dentro de ella.
  • scas2.asm - Lee una cadena y busca un caracter dentro de ella.

Entre otros que hasta vergüenza me da ponerlos si no se lo que hacen :-(,... creo que esta vez, ni la suerte me ayudará.

[actualizado]

He aquí mi horrible programación bajo presión...

  • Aplicación que permita leer el nombre y calificació de 5 alumns, valide si no se repiten los nombres, la calificación tendrá que ser solo de dos digitos, no mayor a 10 ni menor a 0, hmmm,... creo que era todo :-S ¡ho si! también que tenga mucha crema!,... quería una interfáz gráfica agradable al usuario.

Increible pero cierto jeje :P

asm:
.model small
.stack
.data
        nom db 50 dup(' '),'$'  ;Variable para leer el nombre
        cal db 2 dup('0'),'$'   ;Calificación
        sum db 3 dup('0'),'$'   ;Sumatoria para el promedio

        aux db 3 dup('0'),'$'   ;auxiliar
.code
.startup
        call clrScr
        ;1ero
        call leerNombre ;Obtenemos los datos de un usuario
        call leerCalificacion   ;Leemos calificación de primero usuario
        call sumar

        ;2do
        call leerNombre ;Obtenemos los datos de un usuario
        call leerCalificacion   ;Leemos calificación de primero usuario
        call sumar

        ;3ero
        call leerNombre ;Obtenemos los datos de un usuario
        call leerCalificacion   ;Leemos calificación de primero usuario
        call sumar

        ;4to
        call leerNombre ;Obtenemos los datos de un usuario
        call leerCalificacion   ;Leemos calificación de primero usuario
        call sumar

        ;5to
        call leerNombre ;Obtenemos los datos de un usuario
        call leerCalificacion   ;Leemos calificación de primero usuario
        call sumar

        call promedio

.exit
        leerNombre proc c       ;Procedimiento se  *supone* leerá un nombre
                mov cx,0
                mov si,0
                .repeat
                        mov ah,01h      ;Leemos caracter
                        int 21h  ;Ejecutamos la interrupcion para leer carcter
                        cmp al,13
                                je continuar
                        mov nom[si],al  ;Movemos a la cadena el caracter leído
                        inc cx    ;Incrementamos CX, para comparar cuando llegue a 0
                        inc si    ;Incrementamos también si
                .until cx==50
                continuar:
                        mov nom[si],'$' ;Terminamos cadena de caracteres
                call nl ;Salto de línea
                ret     ;Retornamos el control al flujo del programa
        leerNombre endp

        leerCalificacion proc c ;Procedimiento para leer la calificación
                mov cx,0
                mov si,0
                .repeat
                        otro:
                        mov ah,07h      ;Leemos caracter sin eco
                        int 21h  ;Ejecutamos la interrupcion para leer carcter
                        cmp al,13
                                je continuar
                        cmp al,30h
                                jl otro
                        cmp al,39h
                                jg otro
                        mov ah,02h      ;Mostramos digito introducido
                        mov dl,al       ;Movemos caracter a mostrar
                        int 21h  ;Lo mostramos
                        mov cal[si],al  ;Movemos a la cadena el caracter leído
                        inc cx    ;Incrementamos CX, para comparar cuando llegue a 0
                        inc si
                .until cx==2
                continuar:
                        mov cal[si],'$' ;Terminamos la cadena de caracteres

                ;Convertirmos cadena a su valor numérico decimal
               

               
                call nl ;salto de línea
                ret     ;Retornamos el control al flujo del programa

        leerCalificacion endp
       
        clrScr proc c   ;Procedimiento que permite limpiar la pantalla
                mov ah,00h      ;Definimos modo de video
                mov al,03h            ;Seteamos el modo
                int 10h  ;Ejecutamos interrupción
                ret          ;Retornamos el control al flujo del programa
        clrScr endp

        nl proc c       ;Procedimiento para ir a nueva línea
                mov ah,02h            ;Mostrar caracter en pantalla
                mov dl,10                     ;LF
                int 21h   ;Mostramos caracter
                mov dl,13                     ;CR
                int 21h   ;Mostramos caracter
                ret
        nl endp

        sumar proc c    ;Procedimiento que permite llevar el control de la suma para evaluar el promedio
                sub cal,30h     ;48
                mov al,cal
                add sum,al
                add cal,30h     ;48
                ret
        sumar endp

        promedio proc c ;Evalua el promedio      ;Procedimiento que **se supone** **debería** evaluar el promedio en base a sum/5
                mov al,5        ;Movemos el divisor
                div sum  ;Dividimos por AL
               
                mov ah,02h      ;imprimir caracter
                mov dl,al       ;Caracter a imprimir ¿Caracter? ja Estoy enviando cadena :-S
                add dl,30h

                int 21h  ;Ejecutamos la interrupción
                ret
        promedio endp
end
top