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