| gvSIG desktop 1

/*

 * Created on 21-jun-2005

 *

 * To change the template for this generated file go to

 * Window>Preferences>Java>Code Generation>Code and Comments

 */

/* gvSIG. Sistema de Informaci?n Geogr?fica de la Generalitat Valenciana

 *

 * Copyright (C) 2004 IVER T.I. and Generalitat Valenciana.

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public License

 * as published by the Free Software Foundation; either version 2

 * of the License, or (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307,USA.

 *

 * For more information, contact:

 *

 *  Generalitat Valenciana

 *   Conselleria d'Infraestructures i Transport

 *   Av. Blasco Ib??ez, 50

 *   46010 VALENCIA

 *   SPAIN

 *

 *      +34 963862235

 *   gvsig@gva.es

 *      www.gvsig.gva.es

 *

 *    or

 *

 *   IVER T.I. S.A

 *   Salamanca 50

 *   46005 Valencia

 *   Spain

 *

 *   +34 963163400

 *   dac@iver.es

 */

package org.cresques.io.raster;

/**

 * @author Robert Sedgewick and Kevin Wayne

 * Ordenaci?n de los elementos de un vector

 */

public class QuickSort {

        private long comparisons = 0;

        private long exchanges   = 0;

        /***********************************************************************

         *  Quicksort code from Sedgewick 7.1, 7.2.

         ***********************************************************************/

        public void quicksort(int [] a) {

                quicksort(a, 0, a.length - 1);

        }

        public void quicksort(int[] a, int left, int right) { 

                if (right <= left) return;

                int i = partition(a, left, right);

                quicksort(a, left, i-1);

                quicksort(a, i+1, right);

        }

        private int partition(int[] a, int left, int right) {

                int i = left - 1;

                int j = right;

                while(true) { 

                        // find item on left to swap

                        while (less(a[++i], a[right]))

                                ;

                        // find item on right to swap

                        while (less(a[right], a[--j]))

                                if (j == left) break;

                                // check if pointers cross

                        if (i >= j) break;

                        exch(a, i, j);

                }

                // swap with partition element

                exch(a, i, right);

                return i;

        }

        // is x < y ?

        private boolean less(int x, int y) {

                comparisons++;

                return (x < y);

        }

        // exchange a[i] and a[j]

        private void exch(int[] a, int i, int j) {

                exchanges++;

                int swap = a[i];

                a[i] = a[j];

                a[j] = swap;

        }

}