AuK/Teile und Herrsche 1 SS09/JavaQuick

Wiki-Quelltext dieser Seite.

<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>