src/MCview/Zsort.java

   1 /*
   2 * Jalview - A Sequence Alignment Editor and Viewer
   3 * Copyright (C) 2006 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4 *
   5 * This program is free software; you can redistribute it and/or
   6 * modify it under the terms of the GNU General Public License
   7 * as published by the Free Software Foundation; either version 2
   8 * of the License, or (at your option) any later version.
   9 *
  10 * This program is distributed in the hope that it will be useful,
  11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 * GNU General Public License for more details.
  14 *
  15 * You should have received a copy of the GNU General Public License
  16 * along with this program; if not, write to the Free Software
  17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18 */
  19 package MCview;
  20
  21 import java.util.*;
  22
  23
  24 public class Zsort {
  25     public void Zsort(Vector bonds) {
  26         sort(bonds, 0, bonds.size() - 1);
  27     }
  28
  29     public void sort(Vector bonds, int p, int r) {
  30         int q;
  31
  32         if (p < r) {
  33             q = partition(bonds, p, r);
  34             sort(bonds, p, q);
  35             sort(bonds, q + 1, r);
  36         }
  37     }
  38
  39     private int partition(Vector bonds, int p, int r) {
  40         float x = ((Bond) bonds.elementAt(p)).start[2];
  41         int i = p - 1;
  42         int j = r + 1;
  43         Bond tmp;
  44         while (true) {
  45             do {
  46                 j --;
  47             } while ((j >= 0) && (((Bond) bonds.elementAt(j)).start[2] > x));
  48
  49             do {
  50                 i ++;
  51             } while ((i < bonds.size()) &&
  52                     (((Bond) bonds.elementAt(i)).start[2] < x));
  53
  54             if (i < j) {
  55                 tmp = (Bond) bonds.elementAt(i);
  56                 bonds.setElementAt(bonds.elementAt(j), i);
  57                 bonds.setElementAt(tmp, j);
  58             } else {
  59                 return j;
  60             }
  61         }
  62     }
  63 }