|
| 1 | +importorg.algorithm_visualizer.*; |
| 2 | + |
| 3 | +importjava.util.Arrays; |
| 4 | + |
| 5 | +classMain { |
| 6 | + |
| 7 | +privatestaticChartTracerchartTracer =newChartTracer(); |
| 8 | + |
| 9 | +privatestaticLogTracerlogTracer =newLogTracer("Console"); |
| 10 | + |
| 11 | +privatestaticArray1DTracertracer =newArray1DTracer(); |
| 12 | + |
| 13 | +privatestaticInteger[]array = (Integer[])newRandomize.Array1D(15,newRandomize.Integer(1,20)).create(); |
| 14 | + |
| 15 | +publicstaticvoidmain(String[]args) { |
| 16 | +tracer.set(array); |
| 17 | +tracer.chart(chartTracer); |
| 18 | +Layout.setRoot(newVerticalLayout(newCommander[]{chartTracer,tracer,logTracer})); |
| 19 | +logTracer.printf("original array = %s\n",Arrays.toString(array)); |
| 20 | + |
| 21 | +Tracer.delay(); |
| 22 | +quickSort(array,0,array.length -1); |
| 23 | +logTracer.printf("sorted array = %s\n",Arrays.toString(array)); |
| 24 | + } |
| 25 | + |
| 26 | +publicstaticvoidquickSort(Integer[]arr,intleft,intright) { |
| 27 | +intl,r,s; |
| 28 | +while (right >left) { |
| 29 | +l =left; |
| 30 | +r =right; |
| 31 | +s =arr[left]; |
| 32 | +while (l <r) { |
| 33 | +tracer.select(left); |
| 34 | +tracer.select(right); |
| 35 | +Tracer.delay(); |
| 36 | +while (arr[r] >s) { |
| 37 | +tracer.select(r); |
| 38 | +Tracer.delay(); |
| 39 | +tracer.deselect(r); |
| 40 | +r--; |
| 41 | + } |
| 42 | +arr[l] =arr[r]; |
| 43 | +tracer.patch(l,arr[r]); |
| 44 | +Tracer.delay(); |
| 45 | +tracer.depatch(l); |
| 46 | +while (s >=arr[l] &&l <r) { |
| 47 | +tracer.select(l); |
| 48 | +Tracer.delay(); |
| 49 | +tracer.deselect(l); |
| 50 | +l++; |
| 51 | + } |
| 52 | +arr[r] =arr[l]; |
| 53 | +tracer.patch(r,arr[l]); |
| 54 | +Tracer.delay(); |
| 55 | +tracer.depatch(r); |
| 56 | +tracer.deselect(left); |
| 57 | +tracer.deselect(right); |
| 58 | + } |
| 59 | +arr[l] =s; |
| 60 | +tracer.patch(l,s); |
| 61 | +Tracer.delay(); |
| 62 | +tracer.depatch(l); |
| 63 | +quickSort(arr,left,l -1); |
| 64 | +left =l +1; |
| 65 | + } |
| 66 | + } |
| 67 | + |
| 68 | +} |