Metodos de Ordenamiento de vectores

Tipos de Ordenamiento

Ordenamiento interno.
Se lleva a cabo completamente en memoria principal. Todos los objetos que se ordenan caben en la memoria principal de la computadora.

Ordenamiento externo.
No cabe toda la información en memoria principal y es necesario ocupar memoria secundaria. El ordenamiento ocurre transfiriendo bloques de información a memoria principal en donde se ordena el bloque y este es regresado, ya ordenado, a la memoria secundaria.

Hay métodos muy simples de implementar que son útiles en los casos en donde el número de elementos a ordenar no es muy grande. Por otro lado hay métodos sofisticados, más difíciles de implementar pero que son más eficientes en cuestión de tiempo de ejecución. La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, tomandose a n como el número de elementos que tiene el arreglo a ordenar. Ahora se listan los métodos de ordenamiento (Ordenación Interna) que se ilustrarán en este sistema:

Método de Burbuja

Método de Selección

Método de Inserción

Método HeapSort

Método QuickSort

Método MergeSort

Clasificación de los algoritmos de ordenacion.

Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:
La más común es clasificar según el lugar donde se realice la ordenación

Algoritmos de ordenamiento interno: en la memoria del ordenador.
Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.
Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.

Ordenación interna

Los métodos de ordenación interna se aplican principalmente a arreglos unidimensionales. Los principales algoritmos de ordenación interna son:

Selección: Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento. Por ejemplo, si tenemos el arreglo {40,21,4,9,10,35}, los pasos a seguir son:
{4,21,40,9,10,35} <-- Se coloca el 4, el más pequeño, en primera posición : se cambia el 4 por el 40.{4,9,40,21,10,35} <-- Se coloca el 9, en segunda posición: se cambia el 9 por el 21.{4,9,10,21,40,35} <-- Se coloca el 10, en tercera posición: se cambia el 10 por el 40.{4,9,10,21,40,35} <-- Se coloca el 21, en tercera posición: ya está colocado.{4,9,10,21,35,40} <-- Se coloca el 35, en tercera posición: se cambia el 35 por el 40.

Burbuja: El Ordenamiento de Burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo.
Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados. Con el arreglo anterior, {40,21,4,9,10,35}:
Primera pasada:{21,40,4,9,10,35} <-- Se cambia el 21 por el 40.{21,4,40,9,10,35} <-- Se cambia el 40 por el 4.{21,4,9,40,10,35} <-- Se cambia el 9 por el 40.{21,4,9,10,40,35} <-- Se cambia el 40 por el 10.{21,4,9,10,35,40} <-- Se cambia el 35 por el 40.Segunda pasada:{4,21,9,10,35,40} <-- Se cambia el 21 por el 4.{4,9,21,10,35,40} <-- Se cambia el 9 por el 21.{4,9,10,21,35,40} <-- Se cambia el 21 por el 10.
Ya están ordenados, pero para comprobarlo habría que acabar esta segunda comprobación y hacer una tercera. Ejemplo:

void Burbujeo( int A[], int n)
{
int i,j;
for( i=0; i < n-1; i++ )
for( j=n-1; j > i; j--)
if( A[j] < A[j-1] )
Intercambia( &A[j], &A[j-1] );
}

Inserción directa: En este método lo que se hace es tener una sublista ordenada de elementos del arreglo e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada. Para el ejemplo {40,21,4,9,10,35}, se tiene:
{40,21,4,9,10,35} <-- La primera sublista ordenada es {40}.Insertamos el 21:{40,40,4,9,10,35} <-- aux=21;{21,40,4,9,10,35} <-- Ahora la sublista ordenada es {21,40}.Insertamos el 4:{21,40,40,9,10,35} <-- aux=4;{21,21,40,9,10,35} <-- aux=4;{4,21,40,9,10,35} <-- Ahora la sublista ordenada es {4,21,40}.Insertamos el 9:{4,21,40,40,10,35} <-- aux=9;{4,21,21,40,10,35} <-- aux=9;{4,9,21,40,10,35} <-- Ahora la sublista ordenada es {4,9,21,40}.Insertamos el 10:{4,9,21,40,40,35} <-- aux=10;{4,9,21,21,40,35} <-- aux=10;{4,9,10,21,40,35} <-- Ahora la sublista ordenada es {4,9,10,21,40}.Y por último insertamos el 35:{4,9,10,21,40,40} <-- aux=35;{4,9,10,21,35,40} <-- El arreglo está ordenado.

Shell: Es una mejora del método de inserción directa, utilizado cuando el arreglo tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
Por ejemplo, lo pasos para ordenar el arreglo {40,21,4,9,10,35} mediante el método de Shell serían:
Salto=3: Primera pasada: {9,21,4,40,10,35} <-- se intercambian el 40 y el 9. {9,10,4,40,21,35} <-- se intercambian el 21 y el 10.Salto=1: Primera pasada: {9,4,10,40,21,35} <-- se intercambian el 10 y el 4. {9,4,10,21,40,35} <-- se intercambian el 40 y el 21. {9,4,10,21,35,40} <-- se intercambian el 35 y el 40. Segunda pasada: {4,9,10,21,35,40} <-- se intercambian el 4 y el 9.
Con sólo 6 intercambios se ha ordenado el arreglo, cuando por inserción se necesitaban muchos más.

Intercalación: no es propiamente un método de ordenación, consiste en la unión de dos arreglos ordenados de modo que la unión esté también ordenada. Para ello, basta con recorrer los arreglos de izquierda a derecha e ir cogiendo el menor de los dos elementos, de forma que sólo aumenta el contador del arreglo del que sale el elemento siguiente para el arreglo-suma. Si quisiéramos sumar los arreglos {1,2,4} y {3,5,6}, los pasos serían:

Inicialmente: i1=0, i2=0, is=0.Primer elemento: mínimo entre 1 y 3 = 1. Suma={1}. i1=1, i2=0, is=1.Segundo elemento: mínimo entre 2 y 3 = 2. Suma={1,2}. i1=2, i2=0, is=2.Tercer elemento: mínimo entre 4 y 3 = 3. Suma={1,2,3}. i1=2, i2=1, is=3.Cuarto elemento: mínimo entre 4 y 5 = 4. Suma={1,2,3,4}. i1=3, i2=1, is=4.Como no quedan elementos del primer arreglo, basta con poner los elementos que quedan del segundo arreglo en la suma:Suma={1,2,3,4}+{5,6}={1,2,3,4,5,6}

Mergesort: Una técnica muy poderosa para el diseño de algoritmos es "Dividir para conquistar". Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases:
Dividir: Se divide el problema en partes más pequeñas.
Conquistar: Se resuelven recursivamente los problemas más chicos.
Combinar: Los problemas mas chicos de combinan para resolver el grande.
Los algoritmos que utilizan este principio son en la mayoría de los casos netamente recursivos como es el caso de mergesort.
El algoritmo de Mergesort es un ejemplo clásico de algoritmo que utiliza el principio de dividir para conquistar. Si el vector tiene más de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace una intercalación de las dos mitades ordenadas. Para el ejemplo {40,21,4,9,10,35}, se tiene:
{40,21,4},{9,10,35} <-- Dividimos el arreglo en dos{40},{21,4},{9,10,35} <-- Dividimos el primer arreglo nuevamente
{40},{21},{4},{9,10,35} <-- {40} ya está ordenado así que dividimos {21,4}{40},{4,21},{9,10,35} <-- {21} y {4} están ordenados así que se intercalan
{4,21,40},{9,10,35} <-- se intercala {40} con {4,21}
{4,21,40},{9},{10,35} <-- Se divide el segundo arreglo en dos
{4,21,40},{9},{10},{35} <-- Se divide el último arreglo en dos
{4,21,40},{9},{10,35} <-- Intercalamos {10} y {35}
{4,21,40},{9,10,35} <-- Intercalamos {9} y {10,35}
{4,9,10,21,35,40} <-- Intercalamos los dos arreglos y obtenemos el resultado final.

Ordenación rápida (quicksort): Este método se basa en la táctica "divide y vencerás", que consiste en ir subdividiendo el arreglo en arreglos más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del arreglo como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el arreglo.
Normalmente se toma como pivote el primer elemento de arreglo, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran. Por ejemplo, para dividir el arreglo {21,40,4,9,10,35}, los pasos serían:
{21,40,4,9,10,35} <-- se toma como pivote el 21. La búsqueda de izquierda a derecha encuentra el valor 40, mayor que pivote, y la búsqueda de derecha a izquierda encuentra el valor 10, menor que el pivote. Se intercambian:{21,10,4,9,40,35} <-- Si seguimos la búsqueda, la primera encuentra el valor 40, y la segunda el valor 9, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote en su lugar (en el número encontrado por la segunda búsqueda, el 9, quedando:{9,10,4,21,40,35} <-- Ahora tenemos dividido el arreglo en dos arreglos más pequeños: el {9,10,4} y el {40,35}, y se repetiría el mismo proceso.

Métodos de Búsqueda.

La recuperación de información es una de las aplicaciones más importantes de las computadoras. La búsqueda de información está relacionada con las tablas para consultas. Estas tablas contienen una cantidad de información que se almacenan en forma de listas de parejas de datos. Por ejemplo un catálogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos en una lista. Existen diferentes tipos de búsqueda, pero en este informe describiremos sólo la de tipo Secuencial y Binaria.

Método de Búsqueda Secuencial:

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.
Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

Supongamos que una lista de elementos almacenados en un vector (array unidimensional). El método sencillo de buscar un elemento en un vector es explorar secuencialmente el vector, o dicho entre otras palabras recorrer el vector desde el primer elemento hasta el último. Si se encuentra el elemento buscado visualizar un mensaje similar a ‘fin de búsqueda’, en caso contrario visualizar un mensaje similar a ‘elemento no existe en la lista’.
En otras palabras, la búsqueda secuencial compara cada elemento del vector con el valor deseado, hasta que este se encuentra o se termina de leer el vector completo. La búsqueda secuencial no requiere ningún requisito por parte del vector y, por consiguiente, no necesita estar ordenado. El recorrido del vector se realizará normalmente con estructuras repetitivas.

Método de Búsqueda Binaria:

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado.
Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

En una búsqueda secuencial se comienza con el primer elemento del vector y se busca en el hasta que se encuentra el elemento deseado o sea alcanza el final del vector.
Aunque este puede ser un método adecuado para pocos datos, se necesita una técnica más eficaz para conjuntos grandes de datos.
Si el número de elementos del vector es grande, el algoritmo de búsqueda lineal se ralentizaría en tiempo de un modo considerable. Por ejemplo, si tuviéramos que consultar un nombre en la guía telefónica de una gran ciudad, como Madrid, con una cifra aproximada de un millón de abonados, el tiempo de búsqueda, según el nombre se podría eternizar naturalmente, las personas que viven en esa gran ciudad nunca utilizarán un método de búsqueda secuencial, sino un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades hasta encontrar el elemento buscado.
Si los datos que se buscan están clasificados en un determinado orden, el método citado anteriormente se denomina Búsqueda Binaria.
La búsqueda binaria utiliza un método de ‘divide y vencerás’ para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado, entonces la búsqueda ha terminado. En caso contrario, se determina si el elemento buscado está en la primera o en la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sublista.
El proceso de búsqueda debe terminar normalmente conociendo si la búsqueda ha tenido éxito (se ha encontrado el elemento o bien no ha tenido éxito) no se ha encontrado el elemento, normalmente se deberá devolver la posición del elemento buscado dentro del vector.

Metodos de manejo de archivos

Clases para manejar ficheros en C++

Existen tres clases para manejar ficheros: ifstream, ofstream y fstream. La primera está orientada a ficheros de entrada, la segunda a ficheros de salida, y la tercera puede manejar cualquiera de los dos tipos o ficheros de entrada y salida.

Clase ifstream:El constructor está sobrecargado para poder crear streams de varias maneras:ifstream();
ifstream(const char *name, int mode = ios::in,
int = filebuf::openprot);

El primero sólo crea un stream de entrada pero no lo asocia a ningún fichero. El segundo lo crea, lo asocia al fichero con el nombre "name" y lo abre.
Los parámetros son: el nombre del fichero, el modo, que para ifstream es ios::in por defecto. El tercer parámetro se refiere al buffer, y no nos preocupa de momento.

Clase ofstream:Lo mismo pasa con ofstream, salvo que los valores por defecto de los parámetros son diferentes:ofstream();
ofstream(const char *name, int mode = ios::out,
int = filebuf::openprot);

Clase fstream:fstream(); fstream(const char *name, int mode = ios::in,
int = filebuf::openprot);

Método open:Todas estas clases disponen además del método "open", para abrir el fichero a lo largo de la ejecución del programa.void open(const char *name, int mode,
int prot=filebuf::openprot);
"name" es el nombre del fichero, mode es el modo en que se abrirá, puede ser uno o una combinación del tipo enumerado open_mode, de la clase "ios": enum open_mode { in, out, ate, app, trunc, nocreate,
noreplace, binary };

Cada uno de los valores se pueden combinar usando el operador de bits OR (), y significan lo siguiente:
in: modo de entrada.
out: modo de salida.
ate: abre el fichero y sitúa el cursor al final.
app: modo append, parecido al anterior, pero las operaciones de escritura siempre se hacen al final del fichero.
trunc: si se aplica a ficheros de salida, se creará el fichero si no existe previamente, o se truncará con un tamaño de 0 bytes, si existe.
nocreate: impide crear un fichero si no existe, en ese caso, la función falla.
noreplace: lo ignoro.
binary: abre el fichero en modo binario.
Los tres últimos modos probablemente no son estándar, y es posible que no existan en muchos compiladores.

Método close:void close(); Sencillamente, cierra el fichero asociado a un stream.

Operador >>:
Igual que sucede con el stream estándar cout, el operador de flujo de salida >> se puede usar con streams de salida cuando trabajemos con texto.

Operador <<: Del mismo modo, al igual que sucede con el stream estándar cin, el operador de flujo de entrada <<>

Método de salida put:ostream& put(char ch); Sirve para cualquier stream de salida, e inserta un carácter en el stream.

Método de entrada get:int get();
istream& get(char*, int len, char = '\n');
istream& get(char&);
istream& get(streambuf&, char = '\n');

La primera forma no se recomienda y se considera obsoleta, lee un carácter desde el stream de entrada.
La segunda lee caracteres y los almacena en el buffer indicado en el primer parámetro hasta que se leen "len" caracteres o hasta que se encuentra el carácter indicado en el tercer parámetro, que por defecto es el retorno de línea.
La tercera forma extrae un único carácter en la referencia a char proporcionada.
La cuarta no nos interesa de momento.

Método de entrada getline:istream& getline(char*, int, char = '\n');
Extrae caracteres hasta que se encuentra el delimitador y los coloca en el buffer, elimina el delimitador del stream de entrada y no lo añade al buffer.

Método eof: int eof();
Verifica si se ha alcanzado el final del fichero, devuelve un valor nulo si no es así.

Método clear:void clear(iostate state=0); Cada vez que se produzca una condición de error en un stream es necesario eliminarla, ya que en caso contrario ninguna operación que se realice sobre él tendrá éxisto. Por ejemplo, si llegamos hasta el final de fichero, el stream quedará en estado "eof" hasta que se elimine explícitamente ese estado. Eso se hace mediante el método "clear", sin parámetros dejará el estado en 0, es decir, sin errores.

Los estados posibles se definen en un enumerado:enum io_state { goodbit, eofbit, failbit, badbit };
goodbit: indica que el estado es correcto.
eofbit: indica que se ha detectado fin de fichero.
failbit: indica que una operación sobre el stream ha fallado.
badbit: se activa si falla una operación de escritura de buffers.

Método bad:int bad();Devuelve el estado del bit "badbit".

Método fail:int fail();Devuelve el estado del bit "failbit".

Método good:int good();Devuelve el estado del bit "goodbit".
Ejemplo:
Veamos el ejemplo anterior de mostrar dos veces un fichero, pero esta vez escrito para C++ usando streams:// ejemplo1.cpp: Muestra un fichero dos veces.

#include
#include
using namespace std;
int main() {
ifstream fichero("ejemplo1.cpp");
char c;

while(fichero.get(c)) cout.put(c);
fichero.clear(); // (1)
fichero.seekg(0);
while(fichero.get(c)) cout.put(c);
fichero.close();
cin.get();
return 0;
}
Como vemos en (1), es necesario eliminar el bit de eof, que se ha activado al leer hasta el final del fichero, cuando el último intento de llamar a "get" ha fallado, porque se ha terminado el fichero.

Método is_open:int is_open();Devuelve un valor no nulo si el fichero está abierto.
Método flush:ostream& flush();Realiza las operaciones de escritura pendientes que aún se han realizado sólo en el buffer.

Métodos relacionados con acceso aleatorio.
Disponemos de otro tipo enumerado en ios para indicar movimientos relativos dentro de un stream de acceso aleatorio:enum seek_dir { beg, cur, end};
beg: relativo al principio del fichero.
cur: relativo a la posición actual del cursor dentro del fichero.
end: relativo al final del fichero.

Método seekg:Cambia la posición del cursor en streams de entrada.istream& seekg(streampos pos);
istream& seekg(streamoff offset, seek_dir dir);
La primera forma es para cambiar la posición de modo absoluto. La segunda para cambios relativos, en la que se indica el salto en el primer parámetro y el punto de partida en el segundo, que puede ser cualquiera de los indicados anteriormente: ios::beg, ios::cur o ios::end.

Método seekp:Cambia la posición del cursor en streams de salida.ostream& seekp(streampos pos);
ostream& seekp(streamoff offset, seek_dir);
Lo mismo que seekg, pero aplicado a estream de salida.

Método tellg:streampos tellg();Devuelve la posición actual del cursor dentro de un stream de entrada.

Método tellp:streampos tellp();Devuelve la posición actual del cursor dentro de un stream de salida.

Método read:istream& read(char*, int);
Lee el número de caracteres indicado en el segundo parámetro dendro del buffer suministrado por el primero.

Método gcount:int gcount();
Devuelve el número de caracteres sin formato de la última lectura. Las lecturas sin formato son las realizadas mediante las funciones get, getline y read.

Método write:ostream& write(const char*, int);
Escribe el número de caracteres indicado en el segundo parámetro desde el buffer suministrado por el primero.
Ejemplo:
De nuevo haremos el ejemplo de copiar ficheros, pero esta vez usando streams.// copia.cpp: Copia de ficheros
// Uso: copia
#include
#include
using namespace std;
int main(int argc, char **argv) {
ifstream entrada;
ofstream salida;

char buffer[2048]; // Buffer de 2 Kbytes
int bytesLeidos;
if(argc != 3) {
printf("Usar: copia \n");
return 1;
}
// Abrir el fichero de entrada en lectura y binario
entrada.open(argv[1]);
if(!entrada.good()) {
printf("El fichero %s no existe o no puede ser abierto.\n", argv[1]);
return 1;
}
// Crear o sobreescribir el fichero de salida en binario
salida.open(argv[2]);
if(!salida.good()) {
printf("El fichero %s no puede ser creado.\n", argv[2]);
entrada.close();
return 1;
}
// Bucle de copia:
do {
entrada.read(buffer, 2048);
bytesLeidos = entrada.gcount();
salida.write(buffer, bytesLeidos);
} while(bytesLeidos > 0);
// Cerrar ficheros:
entrada.close();
salida.close();
return 0;
}

Mi autobiografia

Mi nombre es Kathya Betsabe Lopez Jaime, tengo 17 años años, estudio Ingenieria en Sistemas Computacionales.

Caracteristicas internas:
Me considero una persona alegre, muy extrovertida me gusta hacer amistades con gente sincera, con personas que valgan la pena, en la U mi super amiga es Nancy ella es una persona muy sociable y muy sincera es por eso que la considero mi amiga...
Me gusta mucho lo que estoy estudiando, creo que es la carrera de vanguardia y pienso que es bueno aprender lo nuevo, lo que nos va a traer excelentes beneficios como lo es la computacion y sus diferentes ramas de aprendizaje.

Caracteristicas Fisicas:
Soy delgada, mid altura es de 1.65 y peso 115lbs. soy piel morena, el color de mis ojos es cafè.

Mis metas:
En un futuro lo que mas anhelo es ser profesional, desemvolverme en un ambiente laboral del cual pueda obtener los mejores beneficios.