[ Foro de C# ]

Ordenacion de array por seleccion directa

Hola a ver si alguien puede decirme si este codigo es realmente seleccion     directa, yo lo ejecuto y visualizo los datos para ver el orden que siguen y parece que funciona, el codigo lo hago de forma distinta a lo convencional, segun el codigo convencional se arregla el vector y despues cambia el valor, yo en este voy cambiando el valor directamente sin cambiar el indice, por lo demas funciona igual pienso. dejo el codigo para que le echeis un vistazo:

using System;
public class directa
{
  public static void Main()
  {
    int[] numeros={34,56,76,87,90,1};
    int i,j,min,auxiliar;
    for (i=0; i<numeros.Length-1; i++)
    {
      min=i;                
      for (j=i+1; j<numeros.Length; j++)
        if (numeros[j] < numeros[min])           
        {
         auxiliar=numeros[j];
         numeros[j]=numeros[min];
         numeros[min]=auxiliar;       
        }
       foreach (int pantalla in numeros)
         {         
          Console.Write(pantalla);
          Console.WriteLine();                 
         }     
     }        
     for (i=0; i<numeros.Length; i++)
       Console.WriteLine(numeros[i]);     
  }
}

La idea de la selección directa es que en cada pasada buscas el número más pequeño (de los restantes, en la "parte no ordenada" del array) y al final de la pasada lo intercambias por el de la posición "i" (la que actúa de contador).

Tu algoritmo ordena, y se parece mucho a una "selección directa", pero, siendo estrictos, no lo es, puesto que no seleccionas primero el dato para intercambiarlo después, sino que vas intercambiando cada uno que es menor que el dato actual, pero en vez de intercambiar sólo el menor de todos ellos. En este sentido, tu algoritmo se parece más a una "ordenación de burbuja".

Si trabajaras sobre un fichero, en que las escrituras típicamente son mucho más lentas que las lecturas, tu algoritmo, como hace más escrituras que un "selección directa" convencional, resultaría más lento.

Ok amigo nacho, pero segun veo el codigo hace algo igual, en el convencional de seleccion directa tambien tiene que intercambiar los indices, en el que yo escribi en lugar de intercambiar los indices intercambie los datos, me imagino como tú dices que eso es lo que lo haria lento, ya que no es lo mismo cambiar un indice que cambiar el contenido de sus datos, pero el funcionamiento en si creo que és el mismo pero perdiendo mas tiempo. Corrigeme si me equivoco. Gracias y un saludo.

Este es el algoritmo típico de selección directa:

Para i=1 hasta n-1
    menor = i
    Para j=i+1 hasta n
        Si A[j] < A[menor]
            menor = j
    Si menor <> i
        Intercambiar ( A[i], A[menor])

Insisto: se intercambia un único valor, al final de cada pasada, cuando ya has encontrado el menor de los restantes. Por eso el nombre "SELECCIÓN", porque primero buscas uno entre todos.

Tu algoritmo hace intercambios intermedios, con lo que la secuencia de datos en cada pasada intermedia es distinta, y sería más lento en caso de usar un fichero.

Por eso, parece un algoritmo de ordenación válido, pero se parece muchísimo a una burbuja, no tanto a una selección directa. Mira, ésta es una burbuja típica:

Para i=1 hasta n-1
    Para j=i+1 hasta n
        Si A[i] > A[j]
            Intercambiar ( A[i], A[j])

Verás que sí intercambia en cada pasada. La única diferencia entre el tuyo y este es si intercambias cada dato con el anterior o con el inicial.

Si amigo lo he comprendido perfectamente, pero queria decirte que en el de seleccion directa cuando haces las pasada tambien intercambias indices, por ejemplo menor=j, hay se hace un proceso de escritura como dices pero mucho mas rapido que lo que yo intente hacer, yo en lugar de intercambiar los indices intercambie los datos, no se si me equivoco. Gracias y saludos.

Entiendo a lo que te refieres, pero piensa que si estuvieras ordenando datos que estuvieran en un fichero, hacer una operación como "Intercambiar ( A[i], A[j])" supone guardar datos en fichero (2 datos, los dos registros que has intercambiado), mientras que una operación como "menor = j" cambia el valor de una variable de control, que estaría en memoria, no en fichero.

Por eso, si trabajas sobre ficheros, es preferible un algoritmo como el de selección directa (puro) sobre uno como el de burbuja (puro) o sobre tu variante, porque estos dos últimos harían más escrituras (lentas) en fichero.

Si trabajas en memoria, todos ellos son bastante lentos para estructuras con muchos datos, porque tienen un coste cuadrático, y el que uno sea más eficiente u otro ya depende de cada caso concreto (por ejemplo, de si los datos estaban inicialmente muy desordenados o no, etc).

Gracias amigo por tan buena explicacion, te dejo ahora lo que cambie y creo que ahora si seria seleccion directa. echale un vistazo:

using System;

public class directa
{
  public static void Main()
  {
    int[] numeros={34,56,76,87,90,1};
    int i,j,min,auxiliar;
    for (i=0; i<numeros.Length-1; i++)
    {
      min=i;                

      for (j=i+1; j<numeros.Length; j++)
       {
        if (numeros[j] < numeros[min])             
         min=j;
       }
        auxiliar=numeros[i];
        numeros[i]=numeros[min];
        numeros[min]=auxiliar;

        foreach (int pantalla in numeros)
         {
          Console.Write(pantalla);
          Console.WriteLine();
         }         
     }
         for (i=0; i<numeros.Length; i++)
         Console.WriteLine(numeros[i]);     
  }
}

Ahora sí es selección directa. Le falta un detalle: el último "si" del algoritmo, de modo que sólo intercambies valores si realmente el menor que has obtenido está por debajo del valor actual.

En caso contrario, una secuencia que empezara con "3 7 5"  se convertiría en "5 3 7", porque el menor de la secuencia "7 5" es un 5, que intercambiarías a ciegas con el 3 que hay en primer lugar (y que no se debería intercambiar).

Amigo nacho no entendi eso ultimo que me dijiste del ultimo if, yo he puesto la secuencia que tú me dices en mi ejemplo y si me lo ordena, he puesto los valores 3,7,5 y me salen perfectamente ordenado, tambien me he fijado que en la red mucha gente no utiliza ese if que mencionas, no se si es que todavia no lo terminé de entender. Saludos.

Perdona el retraso en contestar, pero motivos familiares graves hacen que mi tiempo sea muy limitado estos días.

Efectivamente, tu algoritmo incluye "min=i;", de modo que siempre considera el primer valor "que ya está ordenado", de modo que si ordena correctamente.

Por tanto, la única cosa mejorable es que ese "Intercambiar(i,min)" se hiciera sólo si "i es distinto de min", para evitar una escritura en caso de que el primer dato fuera el menor de cada pasada. Pero no es nada importante. Con ese cambio (y comentando y retabulando el fuente), quedaría

using System;

public class SeleccionDirecta
{
    public static void Main()
    {
        int[] numeros={34,56,76,87,90,1};
        int i,j,min,auxiliar;
        
        // Para todos los datos del array
        for (i=0; i<numeros.Length-1; i++)
        {
            // Busco el menor en cada pasada
            min=i;                
            for (j=i+1; j<numeros.Length; j++)
            {
                if (numeros[j] < numeros[min])             
                    min=j;
            }
            
            // Si el menor estaba descolocado, lo coloco
            if (min != i)
            {
                auxiliar=numeros[i];
                numeros[i]=numeros[min];
                numeros[min]=auxiliar;
            }

            // Y muestro el progreso
            foreach (int dato in numeros)
                Console.Write(dato+" ");
            Console.WriteLine();
        }
    }
}

Tranquilo amigo nacho, antes que nada estan esos problemas que tienes y espero que todo se soluciones con la ayuda de Dios, no te preocupes por el tiempo en responder, si es dentro de 1 semana no pasa nada, bastante haces con estar pendiente y ayudar a personas como es mi caso.
De nuevo en el tema del codigo que escribi, mi pregunta es: es necesario que ponga ese ultimo if? porque si los datos siempre estan ordenado correctamente no termino de ver su significado, si te es posible a ver si en un ejemplo claro puedes indicarme el porque es necesario, disculpa pero seré un poco burro y no termino de verlo,jejeje.
Tambien aprovecho para decirte que casualidad lo que es la vida, me descargue hace 1 mes un libro de c# por internet, es el que estoy leyendo y da la coincidencia que es el tuyo, asi que agradecerte lo muy bien explicado que está todo, porque a veces he intentado leer libros y las palabras son tan técnicas que no conseguia entender muchas cosas. Bueno espero tu respuesta y a ver si de una vez termino de entender ese ultimo if. SALUDOS Y QUE TODO VAYA BIEN.

La idea es sencilla: imagina que tienes los datos "3 3 7 5" ¿Verdad que los dos primeros números son iguales, y no es necesario intercambiarlos?

Un algoritmo que busque un mínimo, pero que luego no compruebe si el mínimo que ha encontrado es distinto del mínimo anterior, podría intercambiar esos dos "números 3" que hay al principio de los datos anteriores, o, en tu caso, podría partir de datos como "3 7 5", encontrar que el mínimo es un "3", y entonces intercambiarlo con el dato del principio, es decir, consigo mismo (intercambiarías el dato de la posición 0 con el dato de la posición 0).

Por eso, en los algoritmos que buscan un dato en vez de intercambiar a ciegas, suele existir un "if" que verifique si realmente es necesario cambiar el mínimo actual y el anterior, porque quizá no sea necesario, si ese número encontrado es igual que el mínimo anterior, o si incluso se trata exactamente del mínimo anterior en su posición original.

Gracias amigo nacho, ahora mas o menos lo entendi, segun dices es que por ejemplo si los 2 primeros son iguales no tengo que intercambiar esos numeros,no? algo asi entendi. Gracias por el tremendo esfuerzo que haces para ayudarnos.
La verdad yo programe hace muchisimos años en gwbasic, rmcobol y pascal, pero claro cuando la programacion era algo distinta, y siempre me ha gustado y por eso ahora estoy leyendo un poquito y aprovechando el tiempo que uno tiene.
De nuevo gracias y espero que tus problemas familiares se resuelvan muy pronto, de momento sigo leyendo tu libro,jejeje. SALUDOS AMIGO.