Laufzeitverhalten von Sortieralgorithmen darstellen

[master099]

Hi,

wie haben von unserem Lehrer eine main-Methode vorgegeben und sollen dazu die Methode schreiben. Das Programm soll bei beliebigen Sortiermethoden funktionieren und dann das Laufzeitverhalten abbilden.
Ich habe soweit alle Methode fertig, nur bei der Ausgabe komme ich nicht weiter. Sie soll so aussehen:

Bubblesort:
------------------------------------------------------------------------------------------------x
----------------------------------------------------------------------------------------------x
-------------------------------------------------------------------------------------------------x
-----------------------------------------------------------------------------------------------x
-------------------------------------------------------------------------------------------------x

Quicksort:
----------x
----------x
----------x
----------x
----------x

immer 5x, weil es 5 Versuche sind

etc.

hier mein Quellcode (hab jetzt mal nur Bubblesort drin):

import java.util.*;

class Experiment {
 
 	public static void main (String [ ] args) {
 	int numberExperiments = 5; // number of experiments
 	int numberElements = 500; // number of elements in array
 	int maxRand = 1000; // random numbers 0 .. maxRand - 1
 	int scale = 1700; // scale for plotting
 	/* Integer.MAX VALUE)= 2,147,483,647
 	for reference: largest value allowed */
 
 	int [ ] array;
 	Random rd = new Random();
 	int [ ] result = new int [numberExperiments];

 	// --- BubbleSort ---
 	BubbleSort bs = new BubbleSort();
 	for (int i = 0; i < numberExperiments; i++) {
 	
 	array = Utils.allocateRandArray(rd, maxRand, numberElements);

 	bs.sort(array, numberElements);
 	result[i] = bs.count;
 	
 	}
 	
 	Utils.simplePlot("BubbleSort", result /* , scale */);


 	}
}

 class Utils {
 	
 	//Array mit Zufallszahlen fuellen
 	static int[] allocateRandArray(Random rd,  int maxRand, int numberElements) {
 		
 		int[] array = new int [numberElements];;
 		
 		for (int i=0; i<numberElements; i++) {
 			
 		array[i] = rd.nextInt(maxRand);
 		
 		}
 		return array;
 	}
 	
 	//Ausgabe
 	static void simplePlot (String name, int[] result /* , int scale */ ) {
 		
 		System.out.println(name +":");
 		
 		
 		for (int i = 0; i < result[i]; i++) {
 				
 			System.out.print("-");
 		}	
}


 //Bubblesort	
 class BubbleSort {
 	
 	int count = 0; //zaehlt die Schritte
 		
 	public BubbleSort() {
 	}
 		
 	public int[] sort(int[] array, int numberElements) {
   
    int temp;

    for (int i = 0; i < numberElements-1; i = i + 1) {
            
      	for (int j=numberElements-1; j > i; j = j - 1) {
            
        	if (array[j-1] > array[j]) {
            	temp = array[j - 1];                
            	array[j - 1] = array[j];                
            	array[j] = temp; 
            	count++;                  
        	}
      	}
    }
    return array;
  } 
}

Es geht um die Methode "simpleplot"-
Die Variable scale soll die Ausgabe auf 1700 begrenzen, da es bei Bubblesort bei 500 Array-Elementen mehr als 1700 Schritte sind. Ich hab es bis jetzt erstmal ohne scale probiert, aber schon da komm ich nicht weiter ???:L

Bitte um Hilfe

 

[Tissi]

Das Problem liegt in der for-Schleife:

Bei deinem Code werden wahrscheinlich fünf striche gemacht, dann kommt eine ArrayIndexOutOfBoundsException.
Und das kommt so:
Erster Schleifendurchlauf: i=0, result ist die Anzahl der Schritte bei Experiment 1; da 0< result wird ein Strich gemacht.
Zweiter Durchlauf: i=1, result ist die Anzahl der Sschritte bei Experiment 2 --> zweiter Strich
...
beim sechsten Durchlauf ist i = 5, result[5] existiert aber gar nicht. Daher die Exception.

Zur Lösung brauchst du zwei ineinander verschachtelte for-Schleifen; eine, die die 5 Experimente durchgeht, und eine zweite, innere, die die Striche für das jeweilige Experiment macht:

for(int i = 0; i < result.length; i++)
   for(int j = 0; j < result[i]; j++)
      System.out.print("-");

 

[master099]

danke. daran lag es

ich habe nun auch noch andere Sortieralgorithmen drin, aber ich glaube meine Auswertung haut nicht so ganz hin

Quicksort müsste doch viel weniger "-" , d.h. Bewegungen haben als InsertionSort???

Bei 200 oder mehr Elementen im Array sieht man natürlich einen grösseren Unterschied.
Quicksort sollte doch aber auch bei 50 Elementen schon deutlich weniger Bewegungen als InsertionSort haben, oder?

Die Counter sind aber denke ich an den richtigen Positionen, oder irre ich mich da?

import java.util.*;

class Experiment {
 
 	public static void main (String [ ] args) {
 	int numberExperiments = 5; // number of experiments
 	int numberElements = 10; // number of elements in array
 	int maxRand = 1000; // random numbers 0 .. maxRand - 1
 	int scale = 1700; // scale for plotting
 	/* Integer.MAX VALUE)= 2,147,483,647
 	for reference: largest value allowed */
 
 	int [ ] array;
 	Random rd = new Random();
 	int [ ] result = new int [numberExperiments];

 	// --- BubbleSort ----------------------------------------------------------
 	BubbleSort bs = new BubbleSort();
 	for (int i = 0; i < numberExperiments; i++) {
 	
 	array = Utils.allocateRandArray(rd, maxRand, numberElements);

 	bs.sort(array, numberElements);
 	result[i] = bs.count;
	
 	}
 	
 	Utils.simplePlot("BubbleSort", result /* , scale */);
 	System.out.println("");
 	
 	// --- InsertionSort -------------------------------------------------------
 	InsertionSort is = new InsertionSort();
 	for (int i = 0; i < numberExperiments; i++) {
 	
 	array = Utils.allocateRandArray(rd, maxRand, numberElements);

 	is.sort(array, numberElements);
 	result[i] = is.count;
	
 	}
 	
 	Utils.simplePlot("InsertionSort", result /* , scale */);
	System.out.println("");
	
	// --- QuickSort -----------------------------------------------------------
 	QuickSort qs = new QuickSort();
 	for (int i = 0; i < numberExperiments; i++) {
 	
 	array = Utils.allocateRandArray(rd, maxRand, numberElements);


 	qs.sort(array);
 	result[i] = qs.count;
	
 	}
 	
 	Utils.simplePlot("QuickSort", result /* , scale */);
	System.out.println("");

 	}
}

 class Utils {
 	
 	//Array mit Zufallszahlen fuellen
 	static int[] allocateRandArray(Random rd,  int maxRand, int numberElements) {
 		
 		int[] array = new int [numberElements];;
 		
 		for (int i=0; i<numberElements; i++) {
 			
 		array[i] = rd.nextInt(maxRand);
 		
 		}
 		return array;
 	}
 	
 	//Bewegungen plotten
 	static void simplePlot (String name, int[] result /* , int scale */ ) {
 		
 		System.out.println(name +":");
 		
 		for(int i = 0; i < result.length; i++) {
 		
   			
   			for(int j = 0; j < result[i]; j++) {
   			
      			
      			System.out.print("-");
			}
		}	
	}
 	
}

 //Bubblesort	
 class BubbleSort {
 	
 	int count = 0; //zaehlt die Schritte
 		
 	public BubbleSort() {
 	}
 		
 	public int[] sort(int[] array, int numberElements) {
   
    int temp;

    for (int i = 0; i < numberElements-1; i = i + 1) {
            
      	for (int j=numberElements-1; j > i; j = j - 1) {
            
        	if (array[j-1] > array[j]) {
            	temp = array[j - 1];                
            	array[j - 1] = array[j];                
            	array[j] = temp; 
            	count++;                  
        	}
      	}
    }
    return array;
  } 
}


//InsertionSort
class InsertionSort {
	
	int count = 0;
	
	public InsertionSort() {
	}
	
	
	int[] sort(int [] array, int numberElements) {

        for (int i = 1; i < numberElements; i++) {
            
            int j = i;
            int temp = array[j];
            
            while (j > 0 && array[j-1] > temp) {
                
                array[j]=array[j-1];
                j--;
            }
            
            array[j]=temp;
            count++;
        }
        return array;
    }
}

class QuickSort {
	
	int count = 0;
	
	public QuickSort() {
	}
	
	private static int[] array;

	public void sort(int[] a)
    {
        array=a;
        quicksort(0, array.length-1);
    }


    int[] quicksort (int lo, int hi)
    {
        int i=lo, j=hi;
        int x=array[(lo+hi)/2];

        //  Aufteilung
        while (i<=j)
        {    
            while (array[i]<x) i++; 
            while (array[j]>x) j--;
            if (i<=j)
            {
                exchange(i, j);
                i++; j--;
            }
        }	count++;

        // Rekursion
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
        
        return array;
        
    } 


    private static void exchange(int i, int j)
    {
        int t=array[i];
        array[i]=array[j];
        array[j]=t;
    }


}

 

[master099]

hat sich erledigt, haut so hin