JavaQuick

Aus ProgrammingWiki

Archivierte Version vom 2010-04-08T15:37:40+00:00. Aktuelle Version

Quicksort in Java

Der Algorithmus

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

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

}

JavaQuick

Quicksort in Java

Suche