Helsingin yliopisto / Tietojenkäsittelytieteen laitos / 581258-1 Johdatus ohjelmointiin
Copyright © 1998 Arto Wikla.

Hassuja järjestämisalgoritmeja

(Muutettu viimeksi 10.11.1998)

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();
  }
}