Metodo De Seleccion

1. Datos Generales del Trabajo

1.1. Introducción

Ordenar es colocar la información de una manera especial basándonos en un criterio de ordenamiento. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los registros del conjunto ordenado. Un ordenamiento conviene usarlo cuándo se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos.

Es importante destacar que se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, con ventajas y desventajas sobre las demás.

Existen diferentes técnicas de ordenamiento como: El Método Burbuja, que consiste en comparar pares de valores, Método Selección, el cual consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo, y varios métodos más.

En esta investigación realizada hablaremos sobre el método de ordenamiento por Selección uno de los métodos más comunes tratando de hacerlo de una manera sencilla y comprensible.

1.2. Antecedentes

A finales del Siglo pasado, una prestigiosa Consultora publicó un estudio que había realizado para averiguar en qué se consumía la CPU de los ordenadores de las empresas. Sospecho que sobre todo, basó su estudio en clientes con mainframes de IBM, aunque sólo sea por lo sencillo que es en estos sistemas conocer con exactitud, gracias al RMF, lo que consume cualquier programa a lo largo del tiempo.

A pocos entendidos sorprendió que el programa que más recursos consumiera fuera el Selection Sort o Selección (es decir, el programa standard para ordenar los registros de un fichero, Base de Datos, etc.), pero lo chocante fue hasta qué punto lo era: alrededor del 60% de todos los recursos de los ordenadores centrales de las compañías se destinaban a ordenar las cosas (es decir de memoria, porque no se ha conseguido encontrar el documento ni vivo ni muerto, ni en papel ni en la red).

En fin, el Sort es el programa para ordenar ficheros en todo Sistema Operativo que se precie. Y, que yo sepa, en todos ellos se llama igual: SORT. Desde el B1 del NCR Century 200, hasta el MS/DOS, pasando por el MVS, etc.

Toma un fichero (o varios) de entrada, lo clasifica por las claves que se le indican (o por todo el contenido del registro, si no se especifica nada), de forma ascendente o descendente… Y además, en algunos Sistemas como MVS, el propio programa sirve para hacer tratamientos a los ficheros: Unificar ficheros, Dividirlo en varios, Extraer registros… un programa muy completo, como veis. Y que se usa muchísimo.

Cuando usamos un ordenador, continuamente estamos clasificando cosas, o el Sistema Operativo lo hace por nosotros, incluso cuando no nos damos cuenta. Cada vez que, en el Explorador de Ficheros de nuestro Sistema Operativo favorito, damos clic en las cabeceras para ver los ficheros ordenados por fecha, o por nombre o lo que sea, el Sistema invoca internamente al Sort.

Además, todas las Bases de Datos, para poder acceder rápidamente a la información solicitada, requieren tener la información previamente ordenada (o, al menos, tener ordenados los índices de acceso a la información).

Cada vez que se requiere recuperar información de una Base de Datos o un fichero, por ejemplo, presentarla en pantalla, casi siempre se requiere clasificarla, porque los humanos esperamos siempre encontrar la información en cierto orden. Todo fichero que se envíe a algún lugar debe estar ordenado. Los procesos batch que toda empresa realiza (la liquidación de cuentas, la facturación, etc.) suelen requerir clasificar una y otra vez los ficheros intermedios. El Sistema Operativo necesita para funcionar mantener ordenada un montón de información.

En definitiva, para que los Sistemas informáticos funcionen como es debido, se requiere que la información esté clasificada siempre. Y ordenar registros de un fichero o de una Base de Datos es un proceso no muy complicado de entender, pero que consume una enorme cantidad de recursos de máquina.

1.3. Información complementaria

El método del Ordenamiento por Selección (Selection Sort) es, valga la redundancia, un algoritmo de ordenamiento que modifica la ubicación de los componentes de un arreglo o lista para satisfacer algún criterio de ordenamiento preestablecido, siendo los más comunes el orden numérico y lexicográfico.

Si bien este método de ordenamiento no es conocido por ser el más estable o con menor orden de complejidad, es fácil de comprender. Por este motivo es que el Ordenamiento por Selección se utiliza con mucha frecuencia en el ámbito educativo para insertar a la persona en la confección y entendimiento de algoritmos.

El ciclo externo se ejecuta n veces para una lista de n elementos, o sea que para ordenar un vector de n términos, tiene que realizar siempre el mismo número de comparaciones. c(n)= (n2-n)/2 Cada búsqueda requiere comparar todos los elementos no clasificados, de manera que el número de comparaciones c(n) no depende del orden de los términos, si no del número de términos; por lo que este algoritmo presenta un comportamiento constante independiente del orden de los datos. Luego la complejidad es del orden n2.

2. Objetivos

2.1. General

Realizar una investigación sobre el método de ordenamiento por selección, mediante la recopilación de información en diferentes páginas web.

2.2. Específicos

• Investigar detalladamente todo lo referente a este método de ordenamiento.

• Ampliar y fortalecer nuestro conocimiento sobre este tema.

• Conocer ventajas y desventajas del método de ordenamiento por selección.

• Codificar en dev c++ el algoritmo del método de ordenamiento por selección.

• Exponer este tema mediante diapositivas en el aula de clase.

3. Marco Teórico

ORDENAMIENTO POR SELECCIÓN

El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente

...