Versionsvergleich

Aus ProgrammingWiki

Vergleich: 2010-04-08T15:37:40+00:00 → 2012-01-23T14:57:39+00:00

<language>Java</language>
−
== Quicksort in Java ==
−
−
'''Der Algorithmus'''
−
−
<code id="4bbdf8447d420">
−
public class Quicksorter
−
{
−
    private int[] a;
−
    private int n;
−
−
    public void sort(int[] a)
−
    {
−
        this.a=a;
−
        n=a.length;
−
        quicksort(0, n-1);
−
    }
−
−
    private void quicksort (int lo, int hi)
−
    {
−
        int i=lo, j=hi;
−
        int x=a[(lo+hi)/2];
−
−
        //  Aufteilung
−
        while (i<=j)
−
        {    
−
            while (a[i]<x) i++; 
−
            while (a[j]>x) j--;
−
            if (i<=j)
−
            {
−
                exchange(i, j);
−
                i++; j--;
−
            }
−
        }
−
−
        // Rekursion
−
        if (lo<j) quicksort(lo, j);
−
        if (i<hi) quicksort(i, hi);
−
    }
−
−
    private void exchange(int i, int j)
−
    {
−
        int t=a[i];
−
        a[i]=a[j];
−
        a[j]=t;
−
    }
−
    public int[] getArray(){
−
    	return this.a;
−
    }
−
−
}    // end class QuickSorter
−
</code>
−
−
<code id="4bbdf8447dccb" hidden>
−
import java.io.BufferedReader;
−
import java.io.IOException;
−
import java.io.InputStreamReader;
−
import java.math.*;
−
public class Main {
−
−
	
−
	public static void main(String[] args) {
−
		
−
		// Angabe der Listengröße
−
		
−
		System.out.println("Wieviele Werte sollen es denn sein?(Zur Anzeige der Werte bitte maximal 50 Werte verlangen)");
−
		int temp = Integer.parseInt(read());
−
		int a[] = new int[temp];
−
		
−
		// Beginn der Zeitmessung für die Werterzeugung
−
		
−
		long start = System.currentTimeMillis();
−
		
−
		// Erzeugung der Werte mit Zufallszahlen
−
		
−
		for(int i = 0; i < temp; i++){
−
			a[i] =(int)(1+Math.random()*100000);
−
		}
−
		
−
		// Ende der Zeitmessung für die Werterzeugung
−
		
−
		long stop = System.currentTimeMillis();		
−
		double elapsedinput = (stop - start) / 1000.0;
−
      
−
        
−
		if(temp < 51){
−
			System.out.println("Ihr Array unsortiert: ");
−
		
−
			for(int i = 0; i < temp; i++){
−
				System.out.println(a[i] + " ");
−
			}			
−
		}
−
		else
−
        	System.out.println("Die Liste ist zu lang und beeinflusst die Zeitberechnung");
−
		
−
		Quicksorter quick = new Quicksorter();
−
		
−
		//Start der Zeitmessung für das Sortieren
−
		
−
		start = System.currentTimeMillis();
−
		
−
		// Übergabe der Liste an Quicksort
−
		
−
		quick.sort(a);
−
		
−
		 // Ende der Zeitmessung für das Sortieren
−
		
−
		 stop = System.currentTimeMillis();
−
	        double elapsed = (stop - start) / 1000.0;
−
	        
−
	       
−
	        if(temp < 51){
−
	        	System.out.println("\nIhr Array sortiert: ");
−
	        	for(int i = 0; i < temp; i++){
−
	        		
−
				System.out.println(a[i] + " ");
−
				}
−
			}
−
	        else
−
	        	System.out.println("Die Liste ist zu lang und beeinflusst die Zeitberechnung");
−
	        
−
	        System.out.println("Generating input:  " + elapsedinput + " seconds");
−
	        System.out.println("Quicksort: " + elapsed + " seconds");
−
	}
−
	public static String read(){
−
		String temp = "";
−
		BufferedReader eingabe = new BufferedReader( new InputStreamReader(System.in));
−
		try{
−
			temp = eingabe.readLine();
−
		}
−
		catch(IOException e){
−
			System.out.println("Fehler");
−
		}
−
		return temp;
−
	}
−
−
}
−
−
</code>
−
−
<eval id="4bbdf8447e3c9">
−
</eval>