Versionsvergleich
Aus ProgrammingWiki
Vergleich: 2010-04-10T12:22:57+00:00 → 2011-01-10T19:41:03+00:00
<language>Java</language> | |
== Quicksort in Java == | |
'''Der Algorithmus''' | |
<code id="4bbdf8e39a9bd"> | |
| − | public Object Quicksorter () |
| + | void quicksort (int[] a) |
{ | |
| − | private int[] a; |
| − | private int n; |
| + | int n=a.length; |
| + | quicksort(a, 0, n-1); |
| + | } |
| − | public void sort(int[] values) |
| − | { |
| − | a=values; |
| − | n=a.length; |
| − | quicksort(0, n-1); |
| − | for(int i=0; i < a.length; i++) System.out.print(a[i]+ (i < a.length-1 ? "," : "")); |
| − | } |
| + | void quicksort (int[] a, int lo, int hi) |
| + | { |
| + | int i=lo, j=hi; |
| + | int x=a[(lo+hi)/2]; |
| − | 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); |
| + | // Aufteilung |
| + | while (i<=j) |
| + | { |
| + | while (a[i]<x) i++; |
| + | while (a[j]>x) j--; |
| + | if (i<=j) |
| + | { |
| + | exchange(a,i, j); |
| + | i++; j--; |
| + | } |
} | |
| − | private void exchange(int i, int j) |
| − | { |
| − | int t=a[i]; |
| − | a[i]=a[j]; |
| − | a[j]=t; |
| − | } |
| − | |
| − | return this; |
| − | } |
| + | // Rekursion |
| + | if (lo<j) quicksort(a,lo, j); |
| + | if (i<hi) quicksort(a,i, hi); |
| + | } |
| + | void exchange(int[] a, int i, int j) |
| + | { |
| + | int t=a[i]; |
| + | a[i]=a[j]; |
| + | a[j]=t; |
| + | } |
| + | |
| + | void display(int[] a) |
| + | { |
| + | for(int i=0; i < a.length; i++) System.out.print(a[i]+ (i < a.length-1 ? "," : "")); |
| + | } |
</code> | |
| − | <eval id="4bbf141066923"> |
| − | QuickSort = Quicksorter (); |
| − | QuickSort.sort(new int[] {1,42,5,23,6,34}); |
| − | </eval> |
| + | <run id="4bbf141066923"> |
| + | int[] a = new int[] {1,42,5,23,6,5,34,52,911,2,31,4,100}; |
| + | quicksort(a); |
| + | display(a); |
| + | </run> |
Quelle: [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm FH-Flensburg] |