none
Metodo Ordenamiento Quick-sort RRS feed

  • Pregunta

  • Hola muchachos soy nuevo en esto tengo un problema y estoy batallando solo en este codigo de ordenar soy principiante manejando C# no tengo mucha experiencia,pero si he estado leyendo e informándome, el programa es un proyecto escolar basico , manejo C# visual osea Forms y botones* tengo que capturar, mostrar y ordenar por metodo QUICK-SORT en la cual consiste ordenar 3 opciones (ID(numeros), Nombre y Apellido (palabras) ), tengo el codigo de Quick pero solo para ordenar números me falta por ORDENAR PALABRAS.como veran en el codigo guardo por archivos .txt uso de delimitadores, entre otras cosas.

     No se en que estoy fallando a la hora de mandar a declarar las palabras o celdas para ordenar,pues nunca hace la funcion. como comente no tengo mucha experiencia, por el momento es asi como tengo el código pues he estado modificando.

    O me pueden explicar como hacer o convertir a palabras por favor. Muchas Gracias.

          static string[] Quick_1(string[] cadenas, int primero, int ultimo)
            {
                int pivote, izq_det, der_det;
                izq_det = primero;
                der_det = ultimo;

                pivote = Convert.ToInt32(cadenas[primero]);
                //pivote = Convert.ToInt32(cadenas[derecha]);

                while (primero < ultimo)
                {
                    while ((cadenas[ultimo].CompareTo(pivote) >= 0) && (primero < ultimo))
                    {
                        ultimo--;
                    }
                    if (primero != ultimo)
                    {
                        cadenas[primero] = cadenas[ultimo];
                        primero++;
                    }
                    while ((cadenas[primero].CompareTo(pivote) <= 0) && (primero < ultimo))
                    {
                        primero++;
                    }
                    if (primero != ultimo)
                    {
                        cadenas[ultimo] = cadenas[primero];

    ultimo--;
                    }
                }

                cadenas[primero] = pivote.ToString();
                pivote = primero;
                primero = izq_det;
                ultimo = der_det;

                if (primero < pivote)
                {
                    Quick(cadenas, primero, pivote - 1);
                }
                if (ultimo > pivote)
                {
                    Quick(cadenas, pivote + 1, ultimo);
                }
                return cadenas;
            }

    ______________BOTON QUICK_______________________

                                                               

           private void button2_Click(object sender, EventArgs e)//ordenamiento QUICK
            {
                if (posicion == 1)
                {
                    try
                    {
                        string linea_id;
                        StreamReader objReader = new StreamReader("Datos_personales.txt");
                        linea_id = objReader.ReadLine();
                        string[] cadena_quick;
                        string[] palabras = linea_id.Split('|');
                        objReader.Close();
                        dataGridView1.Rows.Clear();
                        cadena_quick = Quick(palabras, palabras.Length, 0);
                        //cadena = Quick(palabras, palabras.Length, 0);

                        StreamWriter sw = new StreamWriter("Datos_personales2.txt");
                        for (int index = 0; index <= (palabras.Length) - 1; index++)
                        {
                            sw.Write(cadena_quick[index] + "|");
                        }
                        sw.Close();  
                        MessageBox.Show("SE HA ORDENADO SEGUN EL PARAMETRO [  QUICK ID ] HACER CLICK EN EL BOTON MOSTRAR PARA VER LOS CAMBIOS");

                    }
                    catch (Exception)
                    {
                        Console.WriteLine("Executing finally block.");
                    }
                }
                if (posicion == 2)
                {
                    try
                    {
                        string linea_nombre;


                        StreamReader objReader = new StreamReader("Datos_personales.txt");
                        linea_nombre = objReader.ReadLine();
                        string[] cadena_quick;
                        string[] palabras = linea_nombre.Split('|');
                        dataGridView1.Rows.Clear();
                        cadena_quick = Quick_1(palabras, palabras.Length, 0);
                        //cadena = Ordenar1(palabras);
                        StreamWriter sw = new StreamWriter("Datos_personales2.txt");
                        for (int index = 0; index <= (palabras.Length) - 1; index++)
                        {
                            sw.Write(cadena_quick[index] + "|");
                        }
                        sw.Close();
                        objReader.Close();
                        MessageBox.Show("SE HA ORDENADO SEGUN EL PARAMETRO [QUICK NOMBRE ] HACER CLICK EN EL BOTON MOSTRAR PARA VER LOS CAMBIOS");
                    }
                    catch (Exception)
                    {
                        Console.WriteLine("Executing finally block.");
                    }

     }
                if (posicion == 3)
                {
                    try
                    {
                        string linea_apellid; 
                        StreamReader objReader = new StreamReader("Datos_personales.txt");
                        linea_apellid = objReader.ReadLine();
                        string[] cadena_quick;
                        string[] palabras = linea_apellid.Split('|');
                        dataGridView1.Rows.Clear();
                        cadena_quick = Quick_2(palabras, palabras.Length, 0);
                        //cadena = Ordenar2(palabras);
                        StreamWriter sw = new StreamWriter("Datos_personales2.txt");
                        for (int index = 0; index <= (palabras.Length) - 1; index++)
                        {
                            sw.Write(cadena_quick[index] + "|");
                        }
                        sw.Close();
                        objReader.Close();
                        MessageBox.Show("SE HA ORDENADO SEGUN EL PARAMETRO [  QUICK APELLIDO  ] HACER CLICK EN EL BOTON MOSTRAR PARA VER LOS CAMBIOS");
                    }
                    catch (Exception)
                    {
                        Console.WriteLine("Executing finally block.");
                    }
                }
            }


    Una disculpa olvide quitar los string[temp*7] *

    domingo, 1 de marzo de 2015 23:01

Respuestas

  • Pues me parece que no lo está haciendo bien porque no veo por ningún lado el uso de IComprarer o IComparable y además no entiendo en lo absoluto qué hace un número 7 metido en el QuickSort.  No utilice números mágicos.  Si ese 7 tiene un propósito, declárelo en una constante con un nombre descriptivo.  Un 7 en el código no me dice nada de nada.

    Finalmente le hago notar que en la práctica uno usa List<T>.Sort(), pero imagino que como está aprendiendo a programar, es de hecho muy bueno que le enseñen de algoritmos de ordenamiento.

    Primero usted parece que tiene un archivo de texto donde cada línea es un registro, y cada valor de una propiedad de dicho registro está separada por |.  Entonces yo comenzaría por definir una clase que represente esto claramente:

    public class Registro
    {
        public int ID { get; set; }
        public string Nombre { get; set; }
        public string Apellido { get; set; }
    }

    Ahora entonces lo que hay que hacer es 3 clases que tengan la lógica de comparación deseada:  Una por cada propiedad.

    //Esta es una clase base para no tener que escribir eso de los nulos en todas las clases comparadoras.
    public abstract class RegistroComparerBase : IComparer<Registro>
    {
        protected abstract int CompareCore(Registro x, Registro y);
        public int Compare(Registro x, Registro y)
        {
            //Dependiendo de si devuelve 1 o -1, los valores nulos estarán al principio o al final de la lista ordenada.
            if (x == null && y == null) return 0;
            else if (x == null) return 1; 1:  Nulo al final.
            else if (y == null) return -1; -1:  Nulo al final.
            else
            {
                //Ni x ni y son nulos.
                return CompareCore(x, y);
            }
        }
    }
    
    //Comparemos por ID:
    public class RegistroIDComparer : RegistroComparerBase
    {
        public override CompareCore(Registro x, Registro y)
        {
            //Cuando llegamos aquí ya sabemos que ni x ni y son nulos.
            //Comparamos por ID.  ID es de tipo int.  el tipo int es comparable.
            return x.ID.CompareTo(y.ID);
        }
    }
    
    //Comparemos por Nombre
    public class RegistroNombreComparer : RegistroComparerBase
    {
        public override CompareCore(Registro x, Registro y)
        {
            //El tipo string es comparable, pero puede ser nulo.
            //Entonces hay que repetir un código muy similar aquí para preguntar cuál es nulo y devolver 1 o -1 dependiento, etc.
            //Se lo dejo de tarea.  Al final, llegamos a algo así:
            return x.Nombre.CompareTo(y.Nombre);
        }
    }
    
    //Comparemos por Apellido
    //Es una clase muy similar a la anterior, pero usando la propiedad Apellido.
    //Le queda de tarea.

    Entonces esos serían los comparadores.  Ahora le explico cómo funcionan:  La función Compare(x, y) devolverá -1 si x es menor que y; 0 si son iguales o 1 si x es mayor que y.  Puede leer lo que dice la documentación de MSDN.

    Si estudia bien el método QuickSort, verá que la información que devuelve la función Compare() es suficiente para implementar QuickSort.

    Prosigo entonces.  Ahora lo que hay que hacer es cargar los datos del archivo de texto.  Según leo, imagino que el contenido del archivo de texto es algo así:

    1|Alberto|Grandez
    2|Nancy|Amador
    3|Katherine|Vargas
    

    Entonces mi código de carga sería algo así:

    List<Registro> datos = new List<Registro>();
    using (StreamReader sr = new StreamReader("Datos_personales.txt"))
    {
        while (!sr.EndOfStream)
        {
            string linea = sr.ReadLine();
            string[] dato = linea.Split('|');
            Registro r = new Registro()
            {
                ID = Convert.ToInt32(dato[0]);
                Nombre = dato[1];
                Apellido = dato[2];
            }
            datos.Add(r);
        }
    }
    //Listo.  La colección datos tiene todos los registros del archivo de texto.
    //Ahora ordenamos por QuickSort.  Parece que usted tiene una variable a nivel de formulario llamada "posicion"
    //que indica el tipo de ordenamiento.
    IComparer<Registro> comparador = null;
    switch (posicion)
    {
        case 1:
            comparador = new RegistroIDComparer();
            break;
        case 2:
            comparador = new RegistroNombreComparer();
            break;
        case 3:
            comparador = new RegistroApellidoComparer();
            break;
    }
    if (comparador == null)
    {
        MessageBox.Show("Selección inválida.");
        return;
    }
    Quick(datos, comparador);
    //Ahora la lista "datos" está ordenada.  Muéstrela en el DataGridView.

    Lo que restaría es programa Quick<T>(List<T> lista, IComparer<T> comparador), que básicamente parte la lista a la mitad y llama al método recursivo que compara los extremos del pedazo de lista (con el comparador) y los intercambia si es necesario, luego parte nuevamente y así sucesivamente hasta que el pedazo de lista tenga 2 o menos elementos.  Le ayudo un poco más:

    public void Quick<T>(List<T> lista, IComparer<T> comparador)
    {
        if (lista == null) throw new ArgumentNullException();
        if (lista.Count == 0) return;
        QuickInternal(lista, comparador, 0, lista.Count);
    }
    
    private void QuickInternal<T>(List<T> lista, IComparer<T> comparador, int inicio, int final)
    {
        //Aquí va la implementación recursiva de QuickSort.
    }
    
    //Esta sería la función a usar para intercambiar valores en la lista.
    private void Swap<T>(List<T> lista, int pos1, int pos2)
    {
        T temp = lista[pos1];
        lista[pos1] = lista[pos2];
        lista[pos2] = temp;
    }


    Jose R. MCP
    Code Samples


    lunes, 2 de marzo de 2015 16:10
    Moderador

Todas las respuestas

  • Pues me parece que no lo está haciendo bien porque no veo por ningún lado el uso de IComprarer o IComparable y además no entiendo en lo absoluto qué hace un número 7 metido en el QuickSort.  No utilice números mágicos.  Si ese 7 tiene un propósito, declárelo en una constante con un nombre descriptivo.  Un 7 en el código no me dice nada de nada.

    Finalmente le hago notar que en la práctica uno usa List<T>.Sort(), pero imagino que como está aprendiendo a programar, es de hecho muy bueno que le enseñen de algoritmos de ordenamiento.

    Primero usted parece que tiene un archivo de texto donde cada línea es un registro, y cada valor de una propiedad de dicho registro está separada por |.  Entonces yo comenzaría por definir una clase que represente esto claramente:

    public class Registro
    {
        public int ID { get; set; }
        public string Nombre { get; set; }
        public string Apellido { get; set; }
    }

    Ahora entonces lo que hay que hacer es 3 clases que tengan la lógica de comparación deseada:  Una por cada propiedad.

    //Esta es una clase base para no tener que escribir eso de los nulos en todas las clases comparadoras.
    public abstract class RegistroComparerBase : IComparer<Registro>
    {
        protected abstract int CompareCore(Registro x, Registro y);
        public int Compare(Registro x, Registro y)
        {
            //Dependiendo de si devuelve 1 o -1, los valores nulos estarán al principio o al final de la lista ordenada.
            if (x == null && y == null) return 0;
            else if (x == null) return 1; 1:  Nulo al final.
            else if (y == null) return -1; -1:  Nulo al final.
            else
            {
                //Ni x ni y son nulos.
                return CompareCore(x, y);
            }
        }
    }
    
    //Comparemos por ID:
    public class RegistroIDComparer : RegistroComparerBase
    {
        public override CompareCore(Registro x, Registro y)
        {
            //Cuando llegamos aquí ya sabemos que ni x ni y son nulos.
            //Comparamos por ID.  ID es de tipo int.  el tipo int es comparable.
            return x.ID.CompareTo(y.ID);
        }
    }
    
    //Comparemos por Nombre
    public class RegistroNombreComparer : RegistroComparerBase
    {
        public override CompareCore(Registro x, Registro y)
        {
            //El tipo string es comparable, pero puede ser nulo.
            //Entonces hay que repetir un código muy similar aquí para preguntar cuál es nulo y devolver 1 o -1 dependiento, etc.
            //Se lo dejo de tarea.  Al final, llegamos a algo así:
            return x.Nombre.CompareTo(y.Nombre);
        }
    }
    
    //Comparemos por Apellido
    //Es una clase muy similar a la anterior, pero usando la propiedad Apellido.
    //Le queda de tarea.

    Entonces esos serían los comparadores.  Ahora le explico cómo funcionan:  La función Compare(x, y) devolverá -1 si x es menor que y; 0 si son iguales o 1 si x es mayor que y.  Puede leer lo que dice la documentación de MSDN.

    Si estudia bien el método QuickSort, verá que la información que devuelve la función Compare() es suficiente para implementar QuickSort.

    Prosigo entonces.  Ahora lo que hay que hacer es cargar los datos del archivo de texto.  Según leo, imagino que el contenido del archivo de texto es algo así:

    1|Alberto|Grandez
    2|Nancy|Amador
    3|Katherine|Vargas
    

    Entonces mi código de carga sería algo así:

    List<Registro> datos = new List<Registro>();
    using (StreamReader sr = new StreamReader("Datos_personales.txt"))
    {
        while (!sr.EndOfStream)
        {
            string linea = sr.ReadLine();
            string[] dato = linea.Split('|');
            Registro r = new Registro()
            {
                ID = Convert.ToInt32(dato[0]);
                Nombre = dato[1];
                Apellido = dato[2];
            }
            datos.Add(r);
        }
    }
    //Listo.  La colección datos tiene todos los registros del archivo de texto.
    //Ahora ordenamos por QuickSort.  Parece que usted tiene una variable a nivel de formulario llamada "posicion"
    //que indica el tipo de ordenamiento.
    IComparer<Registro> comparador = null;
    switch (posicion)
    {
        case 1:
            comparador = new RegistroIDComparer();
            break;
        case 2:
            comparador = new RegistroNombreComparer();
            break;
        case 3:
            comparador = new RegistroApellidoComparer();
            break;
    }
    if (comparador == null)
    {
        MessageBox.Show("Selección inválida.");
        return;
    }
    Quick(datos, comparador);
    //Ahora la lista "datos" está ordenada.  Muéstrela en el DataGridView.

    Lo que restaría es programa Quick<T>(List<T> lista, IComparer<T> comparador), que básicamente parte la lista a la mitad y llama al método recursivo que compara los extremos del pedazo de lista (con el comparador) y los intercambia si es necesario, luego parte nuevamente y así sucesivamente hasta que el pedazo de lista tenga 2 o menos elementos.  Le ayudo un poco más:

    public void Quick<T>(List<T> lista, IComparer<T> comparador)
    {
        if (lista == null) throw new ArgumentNullException();
        if (lista.Count == 0) return;
        QuickInternal(lista, comparador, 0, lista.Count);
    }
    
    private void QuickInternal<T>(List<T> lista, IComparer<T> comparador, int inicio, int final)
    {
        //Aquí va la implementación recursiva de QuickSort.
    }
    
    //Esta sería la función a usar para intercambiar valores en la lista.
    private void Swap<T>(List<T> lista, int pos1, int pos2)
    {
        T temp = lista[pos1];
        lista[pos1] = lista[pos2];
        lista[pos2] = temp;
    }


    Jose R. MCP
    Code Samples


    lunes, 2 de marzo de 2015 16:10
    Moderador
  • Hola usuario Jose , muchas gracias por tu ayuda, y principalmente una disculpa en (string temp5 = cadenas[i * 7 + 4];cadenas[i * 7 + 4] = cadenas[j * 7 + 4];).olvide quitarlo del código no me sirve. (es para el metodo burbuja la cual si funciona y ordena los 3 métodos),una disculpa.

    ha lo que veo del código le entiendo muy bien, tengo conocimiento en programar en C++, CodeBlocks pero a la manera en como me están enseñando c# no me queda claro(es confuso).

    Muchas Gracias por el apoyo lo tomare en cuenta tu ayuda. 


    martes, 3 de marzo de 2015 2:55