Programa Facil: noviembre 2011

domingo, 13 de noviembre de 2011

Busqueda Binaria

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Tipos_de_Busquedas
{
    class Program
    {
        static void Main(string[] args)
        {
            TipoBusqueda TB = new TipoBusqueda();

            List<int> Lista = new List<int>();

            Lista.Add(78);
            Lista.Add(35);
            Lista.Add(243);
            //Lista.Add(2);
            //Lista.Add(65);
            //Lista.Add(4);
            //Lista.Add(243);
            //Lista.Add(12);
            //Lista.Add(1);

            int Buscador = 243;

            Console.WriteLine("BUSQUEDA SECUENCIAL");
            Console.WriteLine();
            Console.WriteLine("El Elemento " + Buscador);
            Console.WriteLine("¿se encuentra en la lista? " + TB.BusquedaBinaria(Buscador, Lista));
            Console.ReadKey();
        }
    }

    class TipoBusqueda
    {

        public bool BusquedaBinaria(int Elemento, List<int> Lista)
        {
            int Tamaño = Lista.Count;
            int Centro, Inferior, Superior;
            Inferior = 0;
            Superior = Tamaño - 1;
            while (Inferior <= Superior)
            {
                Centro = ((Superior - Inferior) / 2 + Inferior);

                if (Lista[Centro] == Elemento)
                {
                    return true;
                }
                else
                {
                    if (Elemento < Lista[Centro])
                    {
                        Superior = Centro - 1;
                    }
                    else
                    {
                        Inferior = Centro + 1;
                    }
                }
            }
            return false;
        }
    }
}

Busqueda secuencial

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Tipos_de_Busquedas
{
    class Program
    {
        static void Main(string[] args)
        {
            TipoBusqueda TB = new TipoBusqueda();

            List<int> Lista = new List<int>();

            Lista.Add(78);
            Lista.Add(35);
            Lista.Add(243);
            Lista.Add(2);
            Lista.Add(65);
            Lista.Add(4);
            Lista.Add(243);
            Lista.Add(12);
            Lista.Add(1);

            int Buscador = 243;
            int Elemnto = 20;

            Console.WriteLine("BUSQUEDA SECUENCIAL");
            Console.WriteLine();
            Console.WriteLine("El elemento " + Elemnto);
            Console.WriteLine("¿se encuentra en la lista? " + TB.BusquedaSecuencial(Elemnto, Lista));
            Console.ReadKey();
        }
    }

    class TipoBusqueda
    {
        public bool BusquedaSecuencial(int Elemento, List<int> Lista)
        {
            int Tamaño = Lista.Count;
            int Posicion = 0;

            while (Posicion < Tamaño)
            {
                if (Lista[Posicion] == Elemento)
                {
                    return true;
                }
                else
                {
                    Posicion++;
                }
            }
            return false;
        }
    }
}

sábado, 5 de noviembre de 2011

Método de Ordenamiento ShellSort¡¡

Debe su nombre al ingeniero y matemático estadounidense Donald Shell, que lo publicó en la revista Communications of the ACM en 1959.

Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el des elección directa o el de inserción directa.

Sin embargo, es necesario romper una lanza a favor del algoritmo ShellSort, ya que es el mejor algoritmo de ordenación in-situ... es decir, el mejor de aquellos en los que la cantidad de memoria adicional que necesita -aparte de los propios datos a ordenar, claro está- es constante, sea cual sea la cantidad de datos a ordenar. El algoritmo de la burbuja, el de selección directa, el de inserción directa y el de Shell son todos in-situ, y éste último, el de Shell, es el que mejor resultados da, sin ninguna duda de todos ellos y sus posibles variantes.

El ShellSort es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. El método se denomina “shell” –en honor de su inventor Donald Shell – y también método de inserción con incrementos decrecientes.

En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño - por ejemplo -, hay que ejecutar muchas comparaciones antes de colocarlo en su lugar definitivamente. Shell modifico los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con eso se conseguía la clasificación más rápida. El método se basa en fijar el tamaño de los saltos constantes, pero de más de una posición.

Considere un valor pequeño que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios.

Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna.

Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).

Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 8, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así:

13 14 94 33 82

25 59 94 65 23

45 27 73 25 39

Entonces ordenamos cada columna, lo que nos da

10 14 73 25 23

13 27 94 33 39

25 59 94 65 82

Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).

El Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste."

Aquí esta el pseudo código:

Aquí esta el código en C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ShellSort
{
class Program
{
static void Main(string[] args)
{
ShellSort SS = new ShellSort();
Console.ReadKey();
}
}

class ShellSort
{
List<int> Lista;
public ShellSort()
{
Lista = new List<int>();
Lista.Add(5);
Lista.Add(4);
Lista.Add(7);
Lista.Add(0);
Lista.Add(2);
Lista.Add(8);
Lista.Add(6);
Lista.Add(9);
Lista.Add(1);
Lista.Add(3);
Console.WriteLine("Lista desordenada");
Console.WriteLine();
Mostrar();
Console.WriteLine();
Console.WriteLine("Lista ordenada");
Metodo_ShellSort(Lista);
Mostrar();
}

private void Metodo_ShellSort(List<int> Lista)
{
int incremento, current, hold, i;
if (Lista.Count != 0)
{
incremento = Lista.Count / 2;
while (incremento != 0)
{
current = incremento;

while (current < Lista.Count)
{
hold = Lista[current];
i = current - incremento;

while ((i >= 0) && (hold < Lista[i]))
{
Lista[i + incremento] = Lista[i];
i -= incremento;
}

Lista[i + incremento] = hold;
current = current + 1;
}

}
}
}

private void Mostrar()
{
foreach (int Dato in Lista)
{
Console.WriteLine(Dato);
}
}
}
}

Comentar no cuesta nada¡¡

viernes, 4 de noviembre de 2011

Método de Ordenamiento QuickSort (Rápido)

Uno de los problemas más frecuentes con los que se enfrentan los diseñadores de software es la ordenación de una lista de elementos. Ya sea que estés lidiando con una base de datos de direcciones Web, una lista de clientes o el listín telefónico de tu ciudad, seguramente necesitarás ordenarlos de alguna forma para que esos datos te sean útiles. Quicksort es el algoritmo de ordenamiento más rápido del mundo, y hoy te contamos como funciona.

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.

Bueno Aquí esta el código.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuickSort
{
class Program
{
static void Main(string[] args)
{
int n;
Console.WriteLine("Ingrese Tamaño del arreglo a ordenar: ");
n = Int32.Parse(Console.ReadLine());

Metodo_QuickSort MQS = new Metodo_QuickSort(n);
Console.ReadKey();
}
}

class Metodo_QuickSort
{
int nElem;
int[] QuickSort;
public Metodo_QuickSort(int n)
{
nElem = n;
QuickSort = new int[nElem];

Random Datos = new Random();

Console.WriteLine("");
for (int i = 0; i < QuickSort.Length; i++)
{
QuickSort[i] = Datos.Next(n);
}

Console.WriteLine("Lista en desorden");
Console.WriteLine();
Mostrar();
Console.WriteLine();
MetodoQuickSort(QuickSort, 0, nElem - 1);
Console.WriteLine("Lista en orden");
Console.WriteLine();
Mostrar();
}

private void MetodoQuickSort(int[] QuickSort, int Primero, int Ultimo)
{
int Menor, Mayor, Central;
double Pivote;

Central = (Primero + Ultimo) / 2;
Pivote = QuickSort[Central];
Menor = Primero;
Mayor = Ultimo;

do
{
while (QuickSort[Menor] < Pivote) Menor++;
while (QuickSort[Mayor] > Pivote) Mayor--;

if (Menor <= Mayor)
{
int temp;
temp = QuickSort[Menor];
QuickSort[Menor] = QuickSort[Mayor];
QuickSort[Mayor] = temp;
Menor++;
Mayor--;
}
} while (Menor <= Mayor);

if (Primero < Mayor)
{
MetodoQuickSort(QuickSort, Primero, Mayor);
}
if (Menor < Ultimo)
{
MetodoQuickSort(QuickSort, Menor, Ultimo);
}
}
private void Mostrar()
{
for (int i = 0; i < nElem; i++)
{
Console.WriteLine(QuickSort[i]);
}
}
}
}

No olvides dejar tu comentario¡¡

miércoles, 2 de noviembre de 2011

Método de Ordenamiento Burbuja

Método De Ordenamiento Burbuja

Este método consiste en ir comparando cada par de elementos del array o lista e ir moviendo el mayor elemento hasta la última posición, comenzando desde la posición cero.

Una vez acomodado el mayor elemento, prosigue a encontrar y acomodar el segundo más grande comparando de nuevo los elementos desde el inicio de la lista, y así sigue hasta ordenar todos los elementos del arreglo.

Al ser necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, hace que el ordenamiento por burbuja sea uno de los algoritmos más ineficientes que existen. Incluso entre los algoritmos de ordenamiento del mismo orden, otros como el “Ordenamiento por inserción” son considerados más eficientes. Y lo más curioso es que este procedimiento es uno de los más usados para ordenar listas en todos los lenguajes de programación.

Estos serían los pasos a seguir por este algoritmo para ordenar una lista a1, a2, a3,…an.

1. Comparar a1 con a2 e intercambiarlos si a1>a2

2. Seguir hasta que se haya comparado an-1 con an.

3. Repetir el proceso anterior n-1 veces

Pues bueno, supongamos una lista de números desordenada como por ejemplo la siguiente {32, 4, 35, 1} y queremos ordenarla de menor a mayor.

Para ello cogemos el primer par de elementos (32 y 4) y si el segundo es menor que el primero los intercambiamos, en caso contrario, los dejamos tal cual.

Repetimos el procedimiento, ahora con el segundo y tercer elemento de la lista... hasta llegar al final.

Luego volvemos a repetir todo el procedimiento, pero hasta llegar al penúltimo elemento, después repetimos, pero llegamos hasta el antepenúltimo elemento, y así sucesivamente, hasta tener la lista ordenada.

En nuestro ejemplo ({32, 4, 35, 1}):

· Primer recorrido:

32, 4, 35,1 => 4, 32, 35, 1

4,32, 35, 1 => 4, 32, 35, 1

4, 32, 35, 1=> 4, 32, 1, 35

Repetimos desde el inicio, pero sin contar el último elemento

· Segundo recorrido:

4, 32, 1, 35 => 4, 32, 1, 35

4, 32, 1, 35 => 4, 1, 32, 35 =>

Repetimos desde el inicio, pero sin contar los dos últimos elementos

· Tercer recorrido:

4, 1, 32, 35 => 1, 4, 32, 35

Fin del algoritmo. Lista ordenada.

Aquí esta el código

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Burbuja

{

class Program

{

static void Main(string[] args)

{

Metodo_Burbuja MB = new Metodo_Burbuja();

Console.ReadKey();

}

class Metodo_Burbuja

{

public Metodo_Burbuja()

{

List<int> Lista = new List<int>();

Lista.Add(1);

Lista.Add(3);

Lista.Add(6);

Lista.Add(5);

Lista.Add(0);

Lista.Add(8);

Lista.Add(7);

Lista.Add(2);

Lista.Add(4);

Lista.Add(9);

Console.WriteLine("lista en desorden");

Mostrar(Lista);

Console.WriteLine();

Console.WriteLine("Lista Ordenada");

Ordenar(Lista);

Mostrar(Lista);

}

public List<int> Ordenar(List<int> Lista)

{

int Aux, nElem;

nElem = Lista.Count;

if (Lista.Count != 0)

{

for (int i = 0; i < Lista.Count; i++)

{

for (int j = 0; j < nElem-1; j++)

{

if (Lista[j] > Lista[j + 1])

{

Aux = Lista[j];

Lista[j] = Lista[j + 1];

Lista[j + 1] = Aux;

}

nElem--;

}

return Lista;

}

public void Mostrar(List<int> Lista)

{

foreach (int Dato in Lista)

{

Console.WriteLine(Dato);

}