Sortieralgotithmnus

[Guest]

Hallo;
ich habe als Aufgabe folgendes:
Aufgabe 4 a) Erstellen Sie eine Klasse ZufallsArrays. Die Klasse soll folgende
Klassenmethoden zur Verf¨ugung stellen:
• int[] arrayMitWiederholung(int laenge, int n), erzeugt ein Array
der L¨ange laenge, in dem Zahlen aus dem Intervall 1...n in zuf¨alliger
Reihenfolge stehen. In dem Array d¨urfen Wiederholungen vorkommen.
• int[] arrayOhneWiederholung(int n), erzeugt ein Array der L¨ange n-1,
in dem die Zahlen 1,..,n in zuf¨alliger Reihenfolge ohne Wiederholung
verteilt sind.
• void permutation(Object[] a), f¨uhrt a.length zuf¨allige swap-Operationen
auf dem Array a durch, das heißt, die Methode vertauscht n-mal zwei
zuf¨allig gew¨ahlte Eintr¨age des Arrays.
b) Erstellen Sie eine Klasse BubbleSort. Die Klasse soll ¨uber folgende Klassenmethoden
verf¨ugen:
• int bubbleSortNaiv(int[] a), Methode, die mit dem naiven BubbleSort-
Algorithmus aus der Vorlesung das Array a sortiert. Die Methode soll
zus¨atzlich die Anzahl der ben¨otigten Vertauschungen z¨ahlen und als Ergebnis
zur¨uckgeben.
• int bubbleSortOptimiert(int[] a), sortiert mit dem BubbleSort-Algorithmus
von Kapitel 3, Folie 11, das Array a. Die Methode liefert ebenfalls die Anzahl
der ben¨otigten Vertauschungen.
• main(String[] args), main-Methode, die bubbleSortNaiv und bubbleSortOptimiert
anhand Arras vergleicht, die mit der Methode arrayMitWiederholung aus
Teil a) erstellt wurden. Mit den Methoden sollen 1000 Arrays der L¨ange
1000 sortiert werden, anschließend soll auf der Konsole die durchschnittlich
ben¨otigte Anzahl der Vertauschungen ausgegeben werden.

Es ist auch alles soweit von mir bearbeitet bis auf die main methode.. Ich wei einfach nicht wie ich auf da Array zugreifen soll...
Kann mir bitte emand helfen?? Ist echt wichtig. Danke! Hier ist der Code:

package zettel03;

/**
 * Beschreibung der Klasse ZufallsArrays:
 * Die Klasse Zufallsarray stellt verschiedene Methoden
 * zur Verfügung, um Arrays zu erzeugen.
 * 
 * @author Team 2
 * @version 28.04.2005
 */

public class ZufallsArrays{
//======================================================    
// Klassen-Felder und -Methoden
//======================================================    
    /**
     * erzeugt ein Array der Länge länge, in dem Zahlen aus dem Intervall 1...n
     * in zufälliger Reihenfolge stehen
     * 
     * @param laenge Länge des Array
     * @param n obere Intervallgrenze
     */
    static int [] arrayMitWiederholung(int laenge, int n){
       int[] arrayMW = new int[laenge];
       for(int i=0; i<arrayMW.length; i++)
            arrayMW[i] = (int) Math.round(Math.random()*n+0.5);
       return arrayMW;
    }
        
     /**
      * Methode, die ein Array der Länge n-1 erzeugt, 
      * in dem die Zahlen 1 .... n in zufälliger
      * Reihenfolge ohne Wiederholung verteilt sind.
      * 
      * @param n obere Intervallgrenze
      */  
     static int[] arrayOhneWiederholung(int n){
         int[] arrayOW = new int[n];
         arrayOW[0] = (int) Math.round(Math.random()*n+0.5);
         int i;
         for(i=1; i<arrayOW.length; i++){
            arrayOW[i] = (int) Math.round(Math.random()*n+0.5);
            while(enthaelt(arrayOW[i], arrayOW, i-1))
                    arrayOW[i] = (int) Math.round(Math.random()*n+0.5);
         }
         return arrayOW;
     }
     
     /**
      * Hilfsmethode, die überprüft, ob die zufällig
      * erzeugte Zahl bereits im Array vorhanden ist.
      * 
      * @param elt erzeugte Zufallszahl
      * @param array zu durchsuchender Array
      * @param bis Index, bis zu dem das Array zu durchsuchen ist
      */
     static boolean enthaelt(int elt, int[] array, int bis){
         int i=0;
         while(i<=bis){
             if(array[i] == elt)
                return true;
             else
                i++;
         }
         return false;
     }
     /**
      * Methode, die zufällige swap-Operationen auf dem Array
      * durchführt.
      * 
      * Anmerkung: noch wird nicht darauf geachtet, ob für i und j
      * zufällig dieselben Zahlen erzeugt werden und somit ein und
      * dasselbe Feld mit sich selbst quasi vertauscht wird.
      * Dies könnte man noch zusätzlich überprüfen und für den
      * Fall der Gleichheit eine erneute Zufallszahlenerzeugung
      * durchführen!
      * 
      * @param a Array, auf dem die swap Operationen durchgeführt werden sollen.
      */
     static void permutation(Object[] a){
         int laenge = a.length;
         int i = (int) Math.round(Math.random()*laenge);
         int j = (int) Math.round(Math.random()*laenge);
         swap(a, i, j);
     }  
     
     
     /**
      * Hilfsmethode, die zwei Elemente miteinander vertauscht.
      * 
      * @param a Objekt, in dem die Elemente vertauscht werden sollen
      * @param i Index des ersten zu vertauschenden Elements
      * @param j Index des zweiten zu vertauschenden Elements
      */
     static void swap(Object[] a, int i, int j){
         Object temp = a[i];
         a[i] = a[j];
         a[j] = temp;
     }
//======================================================    
// Objekt-Felder
//======================================================
//======================================================    
// Konstruktor(en) 
//======================================================         
     
     /**
     * Default-Konstruktor für Objekte der Klasse ZufallsArrays
     */
    public ZufallsArrays()
    {
    //Objektvariablen initialisieren    
    }
//======================================================    
// Objekt-Methoden
//======================================================
}

package zettel03;

/**
 * Beschreiben Sie hier die Klasse BubbleSort.
 * Klasse, die mit Hilfe von BubbleSort diverse Arrays sortiert.
 * 
 * @author Team 2
 * @version 28.04.2005
 */
public class BubbleSort extends ZufallsArrays{
//======================================================    
// Klassen-Felder und -Methoden
//====================================================== 
    /**
     * Methode, die mit dem naiven BubbleSort-Algorithmus
     * aus der VL das Array a sortiert.
     * 
     * @param a zu sortierendes Array
     * @return benötigte Vertauschungen
     */
    static int bubbleSortNaiv(int[] a){
        int tauschAnzahl = 0;
        while(!isSorted(a, 0, a.length-1)){
            for(int i=0; i<a.length-1; i++){
                if(a[i] > a[i+1]){
                    swap(a, i, i+1);
                    tauschAnzahl +=1;
                }
            }
        }
        assert isSorted(a, 0, a.length-1): "Array ist nicht sortiert!";
        return tauschAnzahl;
    }
    
    /**
     * Testmethode für Christina: Kannst Du löschen, wenn Du's gesehen hast :-)
     * Hier wird ein Array erzeugt und dann vor und nach der Sortierung verglichen,
     * so daß wir sehen können, daß es tatsächlich auch funktioniert :-)
     */
    static int[] erzeuge(){
        int[] array = new int[10];
        for(int i=0; i<10; i++)
            array[i] = (int) Math.round(Math.random()*5);
        int[] array2 = new int[10];
        array2=array;
        for(int i=0; i<10; i++)
           System.out.println(array2[i]);
        bubbleSortNaiv(array);
        return array;
        }
    
    /**
     * Hilfsmethode, die überprüft, ob ein Array sortiert ist.
     * 
     * @param a zu überprüfender Array
     * @param lo untere Grenze des Intervalls lo....hi des Array
     * @param hi obere Grenze des Intervalls des Arrays
     */
    static boolean isSorted(int[] a, int lo, int hi){
        for(int k=lo; k<hi; k++){
            if(a[k+1] < a[k])
                return false;
        }
        return true;
    }
    
    /**
      * Hilfsmethode, die zwei Elemente miteinander vertauscht.
      * 
      * @param a Array, in dem die Elemente vertauscht werden sollen
      * @param i Index des ersten zu vertauschenden Elements
      * @param j Index des zweiten zu vertauschenden Elements
      */
     static void swap(int[] a, int i, int j){
         int temp = a[i];
         a[i] = a[j];
         a[j] = temp;
     }
    
    /**
     * Methode, die mit dem BubbleSort-Algorithmus
     * von Kapitel 3 das Array a sortiert.
     * 
     * @param a zu sortierendes Array
     * @return benötigte Vertauschungen
     */
    static int bubbleSortOptimiert(int[] a){
        int tauschAnzahlOpt = 0;
        for(int j=a.length-1; j>0; j--){
            for(int i=0; i<j; i++){
                //assert innere Invariante
                if(a[i] > a[i+1]){
                    swap(a, i, i+1);
                    tauschAnzahlOpt +=1;
                }
                    
            }
        assert isSorted(a, j, a.length-1);
        }
        return tauschAnzahlOpt;
    }
    
    /**
     * Main-Methode, die BubbleSortNaiv und BubbleSortOptimiert
     * anhand des Arrays vergleicht, der mit der Methode arrayMitWiederholung
     * aus Aufgabenteil a erstellt wurde.
     * 
     * @return durchschnittlich benötigte Anzahl der Vertauschungen
     */
    public static void main(String[] args){
           //???????
        
    }
//======================================================    
// Objekt-Felder
//======================================================
//======================================================    
// Konstruktor(en) 
//======================================================             
    /**
     * Default-Konstruktor für Objekte der Klasse BubbleSort
     */
    public BubbleSort()
    {
        // Instanzvariable initialisieren
    }
//======================================================    
// Objekt-Methoden
//======================================================
}

 

[Wildcard]

Zunächst mal die Frage warum du für Klassen die nur aus statischen Methoden bestehst einen public Konstruktor
einfügst??
Zu deiner main:
du musst dir doch nur das gewünschte Array erzeugen z.B:

int[] array = ZufallsArrays.arrayMitWiederholung(100,100);

und dann sortieren:

bubbleSortNaiv(array);

edit:
arrayOhneWiederholungen würd ich so machen.

  static int[] arrayOhneWiederholung(int n)
	{ 
      int[] arrayOW = new int[n]; 
      for(int i=0; i<arrayOW.length; i++)
		{ 
           arrayOW[i] = (int) Math.round(Math.random()*n+0.5); 
		   for(int j=0;j<i;j++)
			   if(arrayOW[j]==arrayOW[i])
                 i--; 
        } 
        return arrayOW; 
    }

 

[Guest]

Keine Ahnung? Weil da steht ich sol Klassenmethoden entwickeln wahrscheinlich...

 

[Wildcard]

Den Konstruktor kannst du wieder löschen.

 

[Guest]

ok, also das ist jetzt meine Main methode:

 public static void main(String[] args){
            int[] array = ZufallsArrays.arrayMitWiederholung(100,100);
            bubbleSortNaiv(array);

aber wie zählt der den jetzt den durchschnittswert von den zwei verschiedenen sortierungen, ich mien mir ist klar das ich jetzt noch hinschreiben muss bubbleSortOpt (array), aber wie macht der ne Durchschnittszähung???

Übrigens: danke schonmal

 

[Wildcard]

Na den rückgabewert von jeder sortierung aufsummieren und am ende durch die Anzahl der Sortierungen teilen...

 

[Guest]

Klingt jetzt vielleicht echt dumm, aber: hä?? Ich steh echt aufm schlauch - ich sitz ja auch schon seit heute morgen nonstop vor der blöden kiste und mach meinen Zettel... :shock:

 

[Wildcard]

public static void main(String[] args)
{
    int counter=0;

    for(int i=0;i<furchtbaroft;i++)
    {
        counter+=bubbleSortNaiv(ZufallsArrays.arrayMitWiederholung(100,100)); 
    }
    System.out.println(counter/furchtbaroft);
}

 

[Guest]

ich bin so doof!

Danke Danke dake!!