Hassuja järjestämisalgoritmeja

Luennolla 9.11.1998 lupailin julkistaa "salaa" muutamia mielettömiä järjestämisalgoritmeja. Tässä siis niitä. Havainnollistavat ehkä keskeytyslauseen (break) ja etenemislauseen (continue) käyttöä?

Klassinen tapaus

public class SatunnaisJarj {
 
   private static long satunnaisJarjesta(int[] taulu) {
     int i;
     long kertoja = 0;
     while (true) {
       for (i=0; i < taulu.length-1; ++i)
         if (taulu[i] > taulu[i+1])
           break;        // ei ollut järjestyksessä
       if (i==taulu.length-1) 
         return kertoja; // valmis!

       int eka  = (int)(Math.random()*taulu.length);
       int toka = (int)(Math.random()*taulu.length);
       int apu = taulu[eka];
       taulu[eka] = taulu[toka];
       taulu[toka] = apu;
       ++kertoja;
     }
   }
 
  public static void main(String[] args) { // testipääohjelma

    int[] a = {40, 20, 50, 10, 30};

    for (int i=0; i<a.length; ++i)
       System.out.print(a[i]+" ");
    System.out.println();

    System.out.println("Vaihdettiin "+satunnaisJarjesta(a)+ " kertaa");

    for (int i=0; i<a.length; ++i)
       System.out.print(a[i]+" ");
    System.out.println();


    int[] b = new int[10];
    for (int i=0; i<b.length; ++i)
      b[i] = (int)(300*Math.random()); // vrt. harj. 15

    for (int i=0; i<b.length; ++i)
       System.out.print(b[i]+" ");
    System.out.println();

    System.out.println("Vaihdettiin "+satunnaisJarjesta(b)+ " kertaa");

    for (int i=0; i<b.length; ++i)
       System.out.print(b[i]+" ");
    System.out.println();

  }
}

Kuplavariantti

public class SatunnaisKuplaJarj {
 
   private static long satunnaisKuplaJarjesta(int[] taulu) {
     int i;
     long kertoja = 0;
     while (true) {
       for (i=0; i < taulu.length-1; ++i)
         if (taulu[i] > taulu[i+1])
           break;        // ei ollut järjestyksessä
       if (i==taulu.length-1) 
         return kertoja; // valmis!

       int ind  = (int)(Math.random()*(taulu.length-1));
       int apu = taulu[ind];
       taulu[ind] = taulu[ind+1];
       taulu[ind+1] = apu;
       ++kertoja;
     }
   }
 
  public static void main(String[] args) { // testipääohjelma

    int[] a = {40, 20, 50, 10, 30};

    for (int i=0; i<a.length; ++i)
       System.out.print(a[i]+" ");
    System.out.println();

    System.out.println("Vaihdettiin "+satunnaisKuplaJarjesta(a)+ " kertaa");

    for (int i=0; i<a.length; ++i)
       System.out.print(a[i]+" ");
    System.out.println();


    int[] b = new int[10];
    for (int i=0; i<b.length; ++i)
      b[i] = (int)(300*Math.random()); // vrt. harj. 15

    for (int i=0; i<b.length; ++i)
       System.out.print(b[i]+" ");
    System.out.println();

    System.out.println("Vaihdettiin "+satunnaisKuplaJarjesta(b)+ " kertaa");

    for (int i=0; i<b.length; ++i)
       System.out.print(b[i]+" ");
    System.out.println();

  }
}

Lottojärjestäminen

public class LottoJarj {

   private static long lottoJarjesta(int[] taulu, int yläraja) {

     int arvontakertojenMäärä=0;

yritäUudelleenAlusta:

     while (true) {

       ++arvontakertojenMäärä;

       // arvotaan taulukkotarjokas:
       int[] yritys = new int[taulu.length];
       for (int i=0; i<yritys.length; ++i)
         yritys[i] = (int)(yläraja*Math.random());

       // sattuuko tarjokas olemaan järjestyksessä?:
       for (int i=0; i < yritys.length-1; ++i)
         if (yritys[i] > yritys[i+1]) // järjestysvirhe!
           continue yritäUudelleenAlusta;

       // oli järjestyksessä!
       // vaan sattuuko löytymään oikeat arvot?:

       boolean [] oliJo = new boolean[taulu.length]; // ovat alussa false

etsiSeuraavaa:

       for (int i=0; i < taulu.length; ++i)
         for (int j=0; j < yritys.length; ++j)
           if (taulu[i]==yritys[j] && !oliJo[j]) {
             oliJo[j] = true;
             continue etsiSeuraavaa;
           }
       for (int i=0; i<oliJo.length; ++i)
          if (!oliJo[i])
            continue yritäUudelleenAlusta;

       // jos tänne päästiin, taulukko on saatu "järjestettyä",
       // kopioidaan tulos parametritaulukkoon:
       for (int i=0; i < taulu.length; ++i)
         taulu[i] = yritys[i];

       return arvontakertojenMäärä;
     }
  }
 
  public static void main(String[] args) { // testipääohjelma

    int[] järjestettävä = new int[5];
    for (int i=0; i<järjestettävä.length; ++i)
      järjestettävä[i] = (int)(10*Math.random());  // vain lukuja 0...9

    for (int i=0; i<järjestettävä.length; ++i)
       System.out.print(järjestettävä[i]+" ");
    System.out.println();

    System.out.println("Taulukko arvottiin "
                       +lottoJarjesta(järjestettävä, 10)+ " kertaa");

    for (int i=0; i<järjestettävä.length; ++i)
       System.out.print(järjestettävä[i]+" ");
    System.out.println();
  }
}