QuickSort.java

Go to the documentation of this file.
00001 import java.awt.*;
00002 
00003 class QuickSort extends Sort
00004 {
00005   private int left;
00006   private int right;
00007 
00008   public void run()
00009   {
00010     this.startTime = System.currentTimeMillis();
00011     //doSort();
00012     //doSort(theArray, left, right);
00013     //inssort(theArray);
00014     this.selectionSort(theArray);
00015     this.showArray();
00016     this.theLabel.setText(this.calcRuntime()+"ms - done!");
00017     this.theLabel.validate();
00018   }
00019 
00020   private void doSort()
00021   {
00022     int pos;
00023     int temp;
00024     System.out.println("Left: "+this.left+"\nRight: "+right);
00025     for(int i=(this.left+1); i<this.right; i++)
00026     {
00027       temp = this.theArray[i];
00028       pos = i;
00029       while ((this.theArray[(pos-1)] > temp) && (pos > this.left))
00030       {
00031         this.theArray[pos] = this.theArray[(pos-1)];
00032         pos--;
00033       }
00034       this.theArray[pos] = temp;
00035 
00036       System.out.println(i+"");
00037       this.showArray();
00038       this.theLabel.setText(this.calcRuntime()+"ms - done!");
00039       this.theLabel.validate();
00040     }
00041   }
00042 
00043   public void inssort(int[] a) {
00044   int pos;
00045   for (int i = 1; i <= a.length - 1; i++) {
00046     pos = binsearch(a, 0, i - 1, a[i]);
00047     move(i, pos, a);
00048   }
00049 }
00050 
00051 private void move(int i, int j, int[] a) {
00052   int tmp = a[i];
00053   for (int g = i; g >= j + 1; g--) {
00054     a[g] = a[g - 1];
00055   }
00056   a[j] = tmp;
00057 }
00058 
00059 private int binsearch(int[] a, int low, int high, int x) {
00060   int mitte = 0;
00061   while (low <= high) {
00062     mitte = (low + high) / 2;
00063     if (a[mitte] == x)
00064       return mitte;
00065     if (a[mitte] < x)
00066       low = mitte + 1;
00067     if (a[mitte] > x)
00068       high = mitte - 1;
00069   }
00070   return low;
00071 }
00072 
00073 /*
00074   private void doSort(int[] a, int l, int r)
00075   {
00076     int lpos;
00077     int rpos;
00078     int tmp;
00079     int pivot;
00080 
00081     pivot = theArray[(l+r) / 2];
00082 
00083     lpos = l;
00084     rpos = r;
00085 
00086     while (lpos <= rpos)
00087     {
00088       while (theArray[lpos] < pivot) lpos++;
00089       while (theArray[rpos] > pivot) rpos--;
00090       if (lpos <= rpos)
00091       {
00092         tmp = theArray[lpos];
00093         theArray[lpos] = theArray[rpos];
00094         theArray[rpos] = tmp;
00095         lpos++;
00096         rpos++;
00097       }
00098     }
00099     this.showArray();
00100     this.theLabel.setText(this.calcRuntime()+"ms");
00101     this.theLabel.validate();
00102 
00103     if (l < rpos) this.doSort(theArray,l,rpos);
00104     if (lpos < r) this.doSort(theArray,lpos,r);
00105   }
00106 */
00107 
00108 
00109 // vertauscht in einem Array die Einträge mit Index x und y
00110 private void vertausche(int[] array, int x, int y){
00111   int zwischenspeicher;
00112   zwischenspeicher = array[x];
00113   array[x] = array[y];
00114   array[y] = zwischenspeicher;
00115 }
00116 
00117 // sucht die Position des Minimums eines Teilarrays
00118 private int minimum(int[] array, int anfang, int ende){
00119   int minIdx = anfang;
00120   for (int index=anfang+1; index<=ende; index++){ //durchlaufe das Array
00121     if (array[index] < array[minIdx]){
00122       minIdx = index;                  //neues Minimum gefunden
00123     }
00124   }
00125   return minIdx;
00126 }
00127 
00128 // sortiert ein Array von Zeichen
00129  public void selectionSort(int[] array){
00130   for (int index=0; index<array.length-1; index++){ //durchlaufe das Array
00131     //suche Minimum des unsortierten rechten Teilarrays
00132     int minIdx = minimum(array, index, array.length-1);
00133     vertausche(array,index,minIdx);
00134   }
00135 }
00136 
00137   public void setSettings(int[] aArray, Panel aPanel, Label aLabel, int al, int ar)
00138   {
00139     this.theArray = aArray;
00140     this.thePanel = aPanel;
00141     this.theLabel = aLabel;
00142     this.left = al;
00143     this.right = ar;
00144   }
00145 
00146 }

Generated on Mon Jun 19 18:04:37 2006 for Doxygen Example (Java) by  doxygen 1.4.5