MÉTODOS DE ORDENAMIENTO

Antes de estudiar algunos de los métodos de ordenamiento es necesario definir el problema y el  entorno en el cual se desea trabajar. Para realizar un ordenamiento se necesita un conjunto de  valores ordenables, es decir, que exista un criterio de ordenamiento, por ejemplo las letras se basan  en el alfabeto, los números en la cantidad representada.  Además se asume que los valores no  están repetidos [ esto solo para efecto de los ejemplos, ya que la presencia de valores repetidos no altera el método ].  Además, se trataran solamente métodos de ordenamiento en los que la instrucción base es la comparación entre dos valores y que se obtiene el ordenamiento por medio de intercambio de valores.   Estas consideraciones son la base de los métodos. Son muchos los métodos de ordenamiento, sin embargo,  en este curso se hará énfasis en los siguientes métodos:    Ordenamiento por selección, por inserción, burbuja. 

Ordenamiento por selección

Este método se basa en la búsqueda del primer mayor / menor, del segundo, del tercero y así sucesivamente hasta agotar la lista de valores a procesar.   El algoritmo de ordenación por selección de una lista tiene los siguientes pasos:

1. Encontrar el mayor elemento de la lista 

2. Intercambiar el mayor elemento con el elemento del subíndice 1

3. A continuación se busca el mayor elemento en la sublista de subíndices de 2 hasta n y se intercambia con el elemento de subíndice 2; por consiguiente, se sitúa el segundo elemento mayor en la posición 2

4. A continuación se busca el elemento mayor en la sublista de 3 hasta n, y así sucesivamente

Ordenamiento por burbuja

Este método es clásico y muy sencillo aunque poco  eficiente.      La  ordenación por burbuja [ bubble sort ] se basa en:

1. La comparación de elementos adyacentes del vector e 

2. Intercambio de sus valores si estos están desordenados

De este modo se dice que los valores más pequeños burbujean hacia la parte superior de la lista [hacia el primer elemento],   mientras que los valores más grandes se hunden hacia el fondo de la lista en el caso de un ordenamiento ascendente. La técnica de ordenación de la lista por burbuja compara elementos consecutivos de la lista de modo que si en una pasada no ocurrieran intercambios, significaría que la lista esta ordenada

Link ordenamiento completo ¡

http://dptocomp.ing.uc.edu.ve/rfernand/GuiasCean/ordenamiento.pdf

METODOS DE ORDENAMIENTO

En computación y matemáticas un algoritmo de ordenamiento recursivo es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.

¿Qué es ordenamiento?

Es la  operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.

El ordenamiento se efectúa con base en el valor de algún campo en un registro.

El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.

Ej. De ordenamientos:

Dir. Telefónico, tablas de contenido, bibliotecas y diccionarios, etc.

El ordenar un grupo de datos significa mover los datos o sus  referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.

¿Cuándo conviene usar un método de ordenamiento?

Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Tipos de ordenamientos:

Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.

Los internos:

Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que  el tiempo  que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc).

Los externos:

Son aquellos en los que los valores a ordenar están en memoria  secundaria  (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición acezada (posición 1, posición 500, etc).

Eficiencia en tiempo de ejecución:

Una medida de eficiencia es:

Contar el # de comparaciones (C)

Contar el # de movimientos de items (M)

Estos están en función de el #(n) de items a ser ordenados.

Un "buen algoritmo" de ordenamiento requiere de un orden nlogn comparaciones.

La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo o vector a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2           

Métodos Simples de Ordenamiento

 Métodos simples:

Método de Burbujeo

Método de Inserción

Método de Selección

BUSQUEDA BINARIA

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.

Datos de entrada:

  vec: vector en el que se desea buscar el dato

  tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.

  dato: elemento que se quiere buscar.

Variables

  centro: subíndice central del intervalo

  inf: límite inferior del intervalo

  sup: límite superior del intervalo

inf = 0

sup = tam-1

Mientras inf <= sup:

  centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción

  Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:

   Si dato < vec[centro] entonces:

    sup = centro - 1

   En caso contrario:

    inf = centro + 1

Fin (Mientras)

Devolver Falso

PAGINAS DE METODOS DE ORDENAMIENTO COMPLETO 

http://delta.cs.cinvestav.mx/~adiaz/anadis/Sorting2.pdf

UML

Lenguaje Unificado de Modelado


Lenguaje Unificado de Modelado (LUM o UML, por sus siglas en inglés, Unified Modeling Language) es el lenguaje de modelado de sistemas de software más conocido y utilizado en la actualidad; está respaldado por el OMG (Object Management Group). Es un lenguaje gráfico para visualizar, especificar, construir y documentar un sistema. UML ofrece un estándar para describir un "plano" del sistema (modelo), incluyendo aspectos conceptuales tales como procesos de negocio y funciones del sistema, y aspectos concretos como expresiones de lenguajes de programación, esquemas de bases de datos y componentes reutilizables.

Es importante resaltar que UML es un "lenguaje de modelado" para especificar o para describir métodos o procesos. Se utiliza para definir un sistema, para detallar los artefactos en el sistema y para documentar y construir. En otras palabras, es el lenguaje en el que está descrito el modelo.
Se puede aplicar en el desarrollo de software entregando gran variedad de formas para dar soporte a una metodología de desarrollo de software (tal como el Proceso Unificado Racional o RUP), pero no especifica en sí mismo qué metodología o proceso usar.
UML no puede compararse con la programación estructurada, pues UML significa Lenguaje Unificado de Modelado, no es programación, solo se diagrama la realidad de una utilización en un requerimiento. Mientras que, programación estructurada, es una forma de programar como lo es la orientación a objetos, sin embargo, la programación orientada a objetos viene siendo un complemento perfecto de UML, pero no por eso se toma UML sólo para lenguajes orientados a objetos.
UML cuenta con varios tipos de diagramas, los cuales muestran diferentes aspectos de las entidades representadas.

UML

Analiza a fondo los objetos y sus interacciones para derivar comportamientos del objeto, atributos
y relaciones con los usuarios

Proporciona un conjunto estandarizado de herramientas para documentar el análisis y diseño de un sistema  

Es un medio eficaz de comunicación  entre el equipo de desarrollo y los usuario.

 

CASOS DE USO

La mejor forma de desarrollar un buen diagrama de caso de uso es mediante entrevista directa con los usuarios o posibles futuros usuarios del sistema, poniendo atención a cada una de las actividades o pasos que se van a ir desarrollando desde un primer momento hasta un momento final.
La elaboración de diagramas de uso ayuda poderosamente a un analista a comprender la forma en que un sistema deberá comportarse, obteniendo los requerimientos desde el punto de vista del usuario.
En todo caso de uso siempre hay un actor, que es quien inicia, y luego otro actor (que puede ser el mismo que inicia el caso de uso o puede ser otro diferente), que recibirá algo por parte del sistema. La representación gráfica es directa, de la siguiente forma:

En la figura anterior, la elipse representa el caso de uso. Las dos figuras en los extremos izquierdo y derecho son los actores que intervienen. El actor que inicia se encuentra a la izquierda del caso de uso, y el que recibe a la derecha. El nombre del actor aparece justo debajo de él, y el nombre del caso de uso aparece ya sea dentro de la elipse o justo debajo de ella. Una línea asociativa conecta a un actor con el caso de uso, y representa la comunicación entre el actor y el caso de uso. La línea asociativa es sólida. El rectángulo envuelve a los casos de uso dentro del sistema.

diagrama de estados
Conforme un sistema interactúa con los usuarios y (posiblemente) con otros sistemas, los objetos que lo conforman pasan por cambios  necesarios para ajustar las interacciones. Por esa razón se necesita contar con un mecanismo para cambios en el modelo. Un cambio en un sistema se da debido a que los objetos que componen dicho sistema modificaron su estado como respuesta a los sucesos y al tiempo. Un diagrama de estados también se conoce como un "motor de estado."

El ícono para el estado, como se aprecia en la Figura 3, es un rectángulo de vértices redondeados, y el símbolo de una transición es una línea continua y una punta de flecha. El círculo relleno se interpreta como el punto inicial de una secuencia de estados, y la diana representa al punto final.
Se puede subdividir el símbolo de la Figura 3 en áreas que muestren el nombre, variables y actividades del estado, de esta forma:

Las variables de estado como cronómetros o contadores son, en ocasiones, de ayuda. Las actividades constan de sucesos y acciones: tres de las más utilizadas son entrada (qué sucede cuando el sistema entra al estado), salida (qué sucede cuando el sistema sale del estado), y hacer (qué sucede cuando el sistema está en el estado). Se pueden agregar otros conforme sea necesario.

A continuación se muestra un ejemplo concreto de un diagrama de estados:

 Como se puede ver en la Figura 5, lo primero que se hace es encender la máquina de fax, con lo cual esta arranca y se encuentra lista en condiciones normales, para realizar el envío de fax, que es el siguiente estado registrado. Cuando se envía un fax –esto es, cuando se encuentra en estado de envío de fax- la máquina de fax anota la fecha y hora en que inició el envío (los valores de las variables de estado "fecha" y "hora"), y también anota el número telefónico así como el nombre del propietario (los valores de las variables de estado "teléfono" y "propietario"). Al encontrarse en este estado, la máquina se encarga de agregar un registro de fecha y hora al fax, número telefónico y nombre del propietario. En otras actividades de este estado, la máquina jalará las hojas, paginará el fax y finalizará la transmisión. Mientras se encuentre en el estado de inactividad, la máquina de fax mostrará la fecha y la hora en una pantalla. Finalmente, cuando ya no se vaya a utilizar la máquina de fax por un periodo determinado, se podrá apagar, siendo este también un estado concreto.