Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-1185314

Sort demos account for operations incorrectly

    XMLWordPrintable

    Details

    • Subcomponent:
    • Resolved In Build:
      1.1
    • CPU:
      sparc
    • OS:
      solaris_2.3
    • Verification:
      Not verified

      Description

      Not that you probably care, but there is a bug in the bidirectional
      bubble sort. You don't reset flipped to false for the second loop...

      So, how come you don't let the regular bubble sort short circuit
      if it completes a loop without swapping?

      In BubbleSort you pause at every loop step. In Bidirectional and QSort,
      you only pause when you swap. If you want to go by the latter reasoning,
      then this is the fastest sorting algorithm :-):

      /*- @(#)CheatAlgorithm.oak 1.0 94/12/12
       * Copyright (c) 1994 FirstPerson.
       */

      /*-
       * A cheater sort demonstration algorithm
       * CheatAlgorithm.oak, Thu Oct 27 10:32:35 1994
       * Jim Graham
       */

      class CheatAlgorithm extends SortAlgorithm {
          void sort(int a[]) {
      for (int i = a.length; --i>=0; ) {
      int highest = a[i];
      int highestindex = i;
      for (int j = 0; j<i; j++) {
      if (StopRequested)
      return;
      if (a[j] > highest) {
      highestindex = j;
      highest = a[j];
      }
      }
      if (highestindex != i) {
      int T = a[i];
      a[i] = a[highestindex];
      a[highestindex] = T;
      }
      pause(i,0);
      }

          }
      }

      If you modify the regular bubble sort to only pause when it swaps, then
      both bubble sorts take about the same amount of time.

        Attachments

          Activity

            People

            Assignee:
            mr Mark Reinhold
            Reporter:
            jag James Gosling (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

              Dates

              Created:
              Updated:
              Resolved:
              Imported:
              Indexed: