Quicksort



    • Hier eine Implementation des Quicksort-Algorithmus in Java.

      Java Source Code

      1. public class QuickSort
      2. {
      3. private static long comparisons = 0;
      4. private static long exchanges = 0;
      5. public static void quicksort(double[] a)
      6. {
      7. shuffle(a);
      8. quicksort(a, 0, a.length - 1);
      9. }
      10. // quicksort von a[left] zu a[right]
      11. public static void quicksort(double[] a, int left, int right)
      12. {
      13. if (right <= left) return;
      14. int i = partition(a, left, right);
      15. quicksort(a, left, i-1);
      16. quicksort(a, i+1, right);
      17. }
      18. private static int partition(double[] a, int left, int right)
      19. {
      20. int i = left - 1;
      21. int j = right;
      22. while (true)
      23. {
      24. while (less(a[++i], a[right])) // Element auf der linken Seite zum tauschen finden
      25. ;
      26. while (less(a[right], a[--j])) // Element auf der rechten Seite zum tauschen finden
      27. if (j == left) break; // Grenzen prüfen
      28. if (i >= j) break;
      29. exch(a, i, j); // tauschen der 2 Elemente
      30. }
      31. exch(a, i, right); // tauschen
      32. return i;
      33. }
      34. // ist x < y ?
      35. private static boolean less(double x, double y)
      36. {
      37. comparisons++;
      38. return (x < y);
      39. }
      40. // tauschen von a[i] und a[j]
      41. private static void exch(double[] a, int i, int j)
      42. {
      43. exchanges++;
      44. double swap = a[i];
      45. a[i] = a[j];
      46. a[j] = swap;
      47. }
      48. // array a[] "shufflen"
      49. private static void shuffle(double[] a)
      50. {
      51. int N = a.length;
      52. for (int i = 0; i < N; i++)
      53. {
      54. int r = i + (int) (Math.random() * (N-i)); // zwischen i und N-1
      55. exch(a, i, r);
      56. }
      57. }
      58. // Testroutine
      59. public static void main(String[] args)
      60. {
      61. double[] a = {7.0, 1.0, 8.0, 2.0, 5.0, 4.0};
      62. System.out.println("Array : ");
      63. for( double d : a )
      64. System.out.printf("%.2f; ", d);
      65. System.out.println();
      66. // sortieren und Zeit messen
      67. long start = System.currentTimeMillis();
      68. quicksort(a);
      69. long stop = System.currentTimeMillis();
      70. double elapsed = (stop - start) / 1000.0;
      71. System.out.println("Quicksort: " + elapsed + " seconds");
      72. System.out.println("Array : ");
      73. for( double d : a )
      74. System.out.printf("%.2f; ", d);
      75. System.out.println();
      76. }
      77. }
      Display All


      ..:: Ausgabe der Testroutine ::..

      Array :

      7,00; 1,00; 8,00; 2,00; 5,00; 4,00;

      Quicksort: 0.002 seconds

      Array :

      1,00; 2,00; 4,00; 5,00; 7,00; 8,00;