Monkeysort

X

xyZman

Bekanntes Mitglied
Hi Community,
Ich habe Probleme mit meinem Sortieralgorithmus.
Er sortiert zwar , jedoch nicht richtig.
Wo habe ich einen Fehler gemacht?
Ich glaube es ist ein Problem der Abbruchbedingung. Denn
ab und zu löst er mir die Reihenfolge richtig.

lg
Flo
Java: 
import AlgoTools.IO;


public class MonkeySort {

  /**
   * Zählt die noetigen Schritte fuer das Sortieren
   */
  private static long schritte;

  /**
   * Liefert eine (Pseudo-)Zufallszahl aus dem Intervall [a,b]
   * oder [b,a], je nach dem, ob a > b oder umgekehrt
   *
   * @param a Grenze 1
   * @param b Grenze 2
   *
   * @return Zufallszahl
   */
  private static int randomNumberFromTo(int v, int w) {
    //Garantiere, dass w >= v
    if(v > w) {
      int tmp = v;
      v = w;
      w = tmp;
    }

    return (int) (Math.random() * (w + 1 - v) + v);
  }

  /**
   * Vertauscht zwei Zufallszahlen aus einem Array,
   * solange bis das Array sortiert ist
   *
   * @param unsortierter Array
   *
   * @return sortierter Array
   */
  public static int[] sort (int[]a){

    //Wahrheitswert, ob Array bereits sortiert ist
    boolean s = MonkeySort.sorted (a);

    //Hilfsvariable
    int tmp;

    //Zufallszahlen
    int x;
    int y;

    while (s==false){
            x = MonkeySort.randomNumberFromTo(0,a.length-1);
            y = MonkeySort.randomNumberFromTo(0,a.length-1);
            tmp = a[x];
            a[x] = a[y];
            a[y] = tmp;
            schritte++;
            s = MonkeySort.sorted(a);
    }


    return a;
  }

  /**
   * Prueft, ob ein Array bereits sortiert ist
   *
   * @param Array
   *
   * @return Wahrheitswert
   */
  public static boolean sorted (int[] a){

    //Laenge des Array
    int n = a.length;

    //Wahrheitswert, ob Array bereits sortiert ist
    boolean s = false;

    for (int i=0; i<a.length-1; i++){
        if (a[i]<=a[i+1]){
            s = true;
        }
        else{
            s = false;
        }
    }
    schritte=schritte+n;

    return s;

  }


  public static void main(String[] args) {

    int[] a;

    a = IO.readInts("Bitte Zahlenfolge eingeben:");
    IO.println(a.length);

    //Sortierte Zahlenfolge
    a = MonkeySort.sort(a);

    IO.print("Sortiert von einem Affen:");
    for (int i=0; i<a.length; i++){
        IO.print(" "+a[i]);
    }
    IO.println();
    IO.print("Anzahl der Schritte:" + schritte);
    IO.println();

    boolean z = MonkeySort.sorted(a);
    if (z==false){
        IO.print("not sorted");
    }
    else{
        IO.print("sorted");
    }
  }


}
 
Zuletzt bearbeitet:
AlexSpritze

AlexSpritze

Bekanntes Mitglied
MMn so:

Java: 
public static boolean sorted (int[] a){
 
    //Laenge des Array
    int n = a.length;

    for (int i=0; i<a.length-1; i++){
        schritte++;
        if (a[i]>a[i+1]){
           return false;
        }
    }

    return true; 
  }

-------

Wenn du aber wirklich über das ganze Array iterieren willst ( ist ja schließlich MonkeySort )
Java: 
boolean s = true;
    for (int i=0; i<a.length-1; i++){
        if (a[i]>a[i+1]){
           return s = false;
        }
    }
schritte = schritte + n;
...
return s

In deiner Version hatte s immer nur den Wahrheitswert des letzten Schleifendurchlaufs, und der hat nichts über die Sortiertheit des gesamten Arrays ausgesagt, deshalb vermutlich die zufällig richtigen Ergebnisse.
 
Zuletzt bearbeitet:

Aktuelle Jobs

Neue Themen


Oben