Mostrando entradas con la etiqueta quick sort en c#. Mostrar todas las entradas
Mostrando entradas con la etiqueta quick sort en c#. Mostrar todas las entradas

Método de Ordenamiento Quick Sort en C#

El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición, en el mundo de habla hispana.

Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
La idea central de este algoritmo consiste en los siguiente:


  • Se toma un elemento x de una posición cualquiera del arreglo.
  • Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.
  • Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

Ejemplo:
      A: 15,67,08,16,44,27,12,35
      Se selecciona A[i]  x=15

Primera pasada (DER-IZQ)
     A[8] >= x 35 >= 15 No hay intercambio
     A[7] >= x 12 >= 15 Si hay intercambio

     A: 12,67,08,16,44,27,15,35

(IZQ-DER)
     A[2] < = X 67 < = 15 Si hay intercambio

     A:12,15,08,16,44,27,67,35

2da. Pasada (DER-IZQ)
     A[6] >= x 27 >= 15 No hay intercambio
     A[5] >= x 44 >= 15 No hay intercambio
     A[4] >= x 16 >= 15 No hay intercambio
     A[3] >= x 08 >= 15 Si hay intercambio

     A: 12,08,15,16,44,27,67,35

Como el recorrido de izquierda a derecha debería iniciarse en la misma posición  donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se  encuentra en la posición correcta.

     A: 12, 08, 15, 16, 44, 27, 67, 35

1er 2do Conjunto

     16, 44, 27, 67, 35
     x16

(DER-IZQ)
     A[8]>=x No hay intercambio
     A[7]>=x No hay intercambio
     A[6]>=x No hay intercambio
     A[5]>=x No hay intercambio

     A: 12, 08, 15, 16, 44, 27, 67, 35
     xß44

(DER-IZQ)
     A[8]>= x Si hay intercambio

     A: 12, 08, 15, 16, 35, 27, 67, 44

(IZQ-DER)
     A[6] < = x No hay intercambio
     A[7] < = x Si hay intercambio
     12, 08, 15, 16, 35, 27, 44, 67
     12, 08, 15, 16, 35, 27, 44, 67
     35, 27, 44, 67
     xß35

(DER-IZQ)
     A[8] >= x No hay intercambio
     A[7] >= x No hay intercambio
     A[6] >= x Si hay intercambio
     12, 08, 15, 16, 27, 35, 44, 67
     12,08
     xß12

(DER-IZQ)
    A[2]>=x Si hay intercambio

EL VECTOR ORDENADO:
    08,12,15,16,27,35,44,67

A continuación veamos un ejemplo en Pseudo-Código Para el Método de Quick Sort 



Ejemplo del Método de Ordenamiento Quick Sort en C# 

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

namespace quicksort
{
    class Class
    {
        static void Main()
        {
            int n;
            Console.WriteLine("Metodo de Quick Sort");
            Console.Write("Cuantos longitud del vector: ");
            n = Int32.Parse(Console.ReadLine());
            llenar b = new llenar(n);
        }
    }

    class llenar
    {
        int h;
        int[] vector;
        public llenar(int n)
        {
            h = n;
            vector = new int[h];
            for (int i = 0; i < h; i++)
            {
                Console.Write("ingrese valor {0}: ", i + 1);
                vector[i] = Int32.Parse(Console.ReadLine());
            }
            quicksort(vector, 0, h - 1);
            mostrar();
        }

        private void quicksort(int[] vector, int primero, int ultimo)
        {
            int i, j, central;
            double pivote;
            central = (primero + ultimo) / 2;
            pivote = vector[central];
            i = primero;
            j = ultimo;
            do
            {
                while (vector[i] < pivote) i++;
                while (vector[j] > pivote) j--;
                if (i <= j)
                {
                    int temp;
                    temp = vector[i];
                    vector[i] = vector[j];
                    vector[j] = temp;
                    i++;
                    j--;
                }
            } while (i <= j);

            if (primero < j)
            {
                quicksort(vector, primero, j);
            }
            if (i < ultimo)
            {
                quicksort(vector, i, ultimo);
            }
        }

        private void mostrar()
        {
            Console.WriteLine("Vector ordenados en forma ascendente");
            for (int i = 0; i < h; i++)
            {
                Console.Write("{0} ", vector[i]);
            }
            Console.ReadLine();
        }
    }
}

Al ejecutar el código muestra el siguiente resultado



7 comentarios:
Etiquetas: , , , , ,

Metodos de Ordenamiento en C#

En computación un algoritmo de ordenamiento 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. 

Ahora veremos los distintos métodos de ordenamiento en c#, aremos un ejemplo de cada uno de los métodos de ordenamiento.

1. Método de Ordenamiento de Inserción directa en C#

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

namespace PruebaVector
{
    class PruebaVector
    {
        private int[] vector;

        public void Cargar()
        {
            Console.WriteLine("Metodo de insercion directa");
            Console.Write("Cuantos longitud del vector:");
            string linea;
            linea = Console.ReadLine();
            int cant;
            cant = int.Parse(linea);
            vector = new int[cant];
            for (int f = 0; f < vector.Length; f++)
            {
                Console.Write("Ingrese elemento "+(f+1)+": ");
                linea = Console.ReadLine();
                vector[f] = int.Parse(linea);
            }
        }

        public void InsercionDirecta()
        {
            int auxili;
            int j;
            for (int i = 0; i < vector.Length; i++)
            {
                auxili = vector[i];
                j = i - 1;
                while (j >= 0 && vector[j] > auxili)
                {
                    vector[j + 1] = vector[j];
                    j--;
                }
                vector[j + 1] = auxili;
            }
        }

        public void Imprimir()
        {
            Console.WriteLine("Vector ordenados en forma ascendente");
            for (int f = 0; f < vector.Length; f++)
            {
                Console.Write(vector[f]+"  ");
            }
            Console.ReadKey();
        }


        static void Main(string[] args)
        {
            PruebaVector pv = new PruebaVector();
            pv.Cargar();
            pv.InsercionDirecta();
            pv.Imprimir();
        }
    }
}

Al ejecutar el código muestra el siguiente resultado



2. Método de Ordenamiento de Inserción Binaria en C# 

                    int auxiliar;
                    int q;
                    int izqui;
                    int dere;
                    for (int i = 0; i < numeros.Length; i++)
                    {
                        auxiliar = numeros[i];
                        izqui = 0;
                        dere = i - 1;
                        while (izqui <= dere)
                        {
                            q = ((izqui + dere) / 2);
                            if (auxiliar < numeros[q])
                            {
                                dere = q - 1;
                            }
                            else
                            {
                                izqui = q + 1;
                            }
                            j = i - 1;
                            while (j >= izqui)
                            {
                                numeros[j + 1] = numeros[j];
                                j = j - 1;
                            }
                            numeros[izqui] = auxiliar;
                        }
                    }
                    for (int i = 0; i < longitud; i++)
                        Console.WriteLine(" " + numeros[i]);


3. Método de Ordenamiento Shell Sort en C#


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

namespace PruebaVector
{
    class PruebaVector
    {
        private int[] vector;

        public void Cargar()
        {
            Console.WriteLine("Metodo de Shell Sort");
            Console.Write("Cuantos longitud del vector:");
            string linea;
            linea = Console.ReadLine();
            int cant;
            cant = int.Parse(linea);
            vector = new int[cant];
            for (int f = 0; f < vector.Length; f++)
            {
                Console.Write("Ingrese elemento "+(f+1)+": ");
                linea = Console.ReadLine();
                vector[f] = int.Parse(linea);
            }
        }

        public void Shell()
        {
            int salto = 0;
            int sw = 0;
            int auxi = 0;
            int e = 0;
            salto = vector.Length / 2;
            while (salto > 0)
            {
                sw = 1;
                while (sw != 0)
                {
                    sw = 0;
                    e = 1;
                    while (e <= (vector.Length - salto))
                    {
                        if (vector[e - 1] > vector[(e - 1) + salto])
                        {
                            auxi = vector[(e - 1) + salto];
                            vector[(e - 1) + salto] = vector[e - 1];
                            vector[(e - 1)] = auxi;
                            sw = 1;
                        }
                        e++;
                    }
                }
                salto = salto / 2;
            }
        }

        public void Imprimir()
        {
            Console.WriteLine("Vector ordenados en forma ascendente");
            for (int f = 0; f < vector.Length; f++)
            {
                Console.Write(vector[f]+"  ");
            }
            Console.ReadKey();
        }


        static void Main(string[] args)
        {
            PruebaVector pv = new PruebaVector();
            pv.Cargar();
            pv.Shell();
            pv.Imprimir();
        }
    }
}

Al ejecutar el código muestra el siguiente resultado


4. Método de Ordenamiento Quick Sort en C#

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

namespace quicksort
{
    class Class
    {
        static void Main()
        {
            int n;
            Console.WriteLine("Metodo de Quick Sort");
            Console.Write("Cuantos longitud del vector: ");
            n = Int32.Parse(Console.ReadLine());
            llenar b = new llenar(n);
        }
    }

    class llenar
    {
        int h;
        int[] vector;
        public llenar(int n)
        {
            h = n;
            vector = new int[h];
            for (int i = 0; i < h; i++)
            {
                Console.Write("ingrese valor {0}: ", i + 1);
                vector[i] = Int32.Parse(Console.ReadLine());
            }
            quicksort(vector, 0, h - 1);
            mostrar();
        }

        private void quicksort(int[] vector, int primero, int ultimo)
        {
            int i, j, central;
            double pivote;
            central = (primero + ultimo) / 2;
            pivote = vector[central];
            i = primero;
            j = ultimo;
            do
            {
                while (vector[i] < pivote) i++;
                while (vector[j] > pivote) j--;
                if (i <= j)
                {
                    int temp;
                    temp = vector[i];
                    vector[i] = vector[j];
                    vector[j] = temp;
                    i++;
                    j--;
                }
            } while (i <= j);

            if (primero < j)
            {
                quicksort(vector, primero, j);
            }
            if (i < ultimo)
            {
                quicksort(vector, i, ultimo);
            }
        }

        private void mostrar()
        {
            Console.WriteLine("Vector ordenados en forma ascendente");
            for (int i = 0; i < h; i++)
            {
                Console.Write("{0} ", vector[i]);
            }
            Console.ReadLine();
        }
    }
}

Al ejecutar el código muestra el siguiente resultado



5. Método de Ordenamiento Burbuja en C#

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

namespace Burbuja
{
    class Burbuja
    {
        private int[] vector;

        public void Cargar()
        {
            Console.WriteLine("Metodo de Burbuja");
            Console.Write("Cuantos longitud del vector: ");
            string linea;
            linea = Console.ReadLine();
            int cant;
            cant = int.Parse(linea);
            vector = new int[cant];
            for (int f = 0; f < vector.Length; f++)
            {
                Console.Write("Ingrese elemento "+(f+1)+": ");
                linea = Console.ReadLine();
                vector[f] = int.Parse(linea);
            }
        }

        public void MetodoBurbuja()
        {
            int t;
            for (int a = 1; a < vector.Length; a++)
                for (int b = vector.Length - 1; b >= a; b--)
                {
                    if (vector[b - 1] > vector[b])
                    {
                        t = vector[b - 1];
                        vector[b - 1] = vector[b];
                        vector[b] = t;
                    }
                }
        }

        public void Imprimir()
        {
            Console.WriteLine("Vector ordenados en forma ascendente");
            for (int f = 0; f < vector.Length; f++)
            {
                Console.Write(vector[f]+"  ");
            }
            Console.ReadKey();
        }

        static void Main(string[] args)
        {
            Burbuja pv = new Burbuja();
            pv.Cargar();
            pv.MetodoBurbuja();
            pv.Imprimir();
        }
    }
}

Al ejecutar el código muestra el siguiente resultado

6. Método de Ordenamiento Shaker Sort en C#

int n = numeros.Length;
            int izq = 1;
            int k = n;
            int aux;
            int der = n;

            do
            {
                for (int i = der; i >= izq; i--)
                {
                    if (numeros[i - 1] > numeros[i])
                    {
                        aux = numeros[i - 1];
                        numeros[i - 1] = numeros[i];
                        numeros[i] = aux;
                        k = i;
                    }
                }
                izq = k + 1;
                for (int i = izq; i <= der; i++)
                {
                    if (numeros[i - 1] > numeros[i])
                    {
                        aux = numeros[i - 1];
                        numeros[i - 1] = numeros[i];
                        numeros[i] = aux;
                        k = 1;
                    }
                }
                der = k - 1;
            }
            while (der >= izq);

            for (int i = 0; i < longitud; i++)
                Console.WriteLine(" " + numeros[i]);


7. Método de Ordenamiento Merge Sort 

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

namespace MergeSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[40];
            Console.WriteLine("Metodo de Merge Sort");
            Console.Write("Cuantos longitud del vector: ");
            string linea;
            linea = Console.ReadLine();
            int cant;
            cant = int.Parse(linea);
            nums = new int[cant];
            for (int f = 0; f < nums.Length; f++)
            {
                Console.Write("Ingrese elemento " + (f + 1) + ": ");
                linea = Console.ReadLine();
                nums[f] = int.Parse(linea);
            }
            MergeSort(nums);
            Console.WriteLine("Vector Ordenado Ascendentemente");
            for (int i = 0; i < nums.Length; i++)
                Console.Write(nums[i] + " ");
            Console.ReadLine();
        }

        //Método portal que llama al método recursivo inicial
        public static void MergeSort(int[] x)
        {
            MergeSort(x, 0, x.Length - 1);
        }

        static private void MergeSort(int[] x, int desde, int hasta)
        {
            //Condicion de parada
            if (desde == hasta)
                return;

            //Calculo la mitad del array
            int mitad = (desde + hasta) / 2;

            //Voy a ordenar recursivamente la primera mitad
            //y luego la segunda
            MergeSort(x, desde, mitad);
            MergeSort(x, mitad + 1, hasta);

            //Mezclo las dos mitades ordenadas
            int[] aux = Merge(x, desde, mitad, mitad + 1, hasta);
            Array.Copy(aux, 0, x, desde, aux.Length);
        }

        //Método que mezcla las dos mitades ordenadas
        static private int[] Merge(int[] x, int desde1, int hasta1, int desde2, int hasta2)
        {
            int a = desde1;
            int b = desde2;
            int[] result = new int[hasta1 - desde1 + hasta2 - desde2 + 2];

            for (int i = 0; i < result.Length; i++)
            {
                if (b != x.Length)
                {
                    if (a > hasta1 && b <= hasta2)
                    {
                        result[i] = x[b];
                        b++;
                    }
                    if (b > hasta2 && a <= hasta1)
                    {
                        result[i] = x[a];
                        a++;
                    }
                    if (a <= hasta1 && b <= hasta2)
                    {
                        if (x[b] <= x[a])
                        {
                            result[i] = x[b];
                            b++;
                        }
                        else
                        {
                            result[i] = x[a];
                            a++;
                        }
                    }
                }
                else
                {
                    if (a <= hasta1)
                    {
                        result[i] = x[a];
                        a++;
                    }
                }
            }
            return result;
        }
    }
}

Al ejecutar el código muestra el siguiente resultado


12 comentarios:
Etiquetas: , , , , , , ,
Suscribirse a: Entradas (Atom)