Application: gvSIG desktop

/*

 * Cresques Mapping Suite. Graphic Library for constructing mapping applications.

 * 

 * Copyright (C) 2004-5. 

 *

 * 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:

 * 

 * cresques@gmail.com

 */

package org.cresques.io.raster;

/**

 * Ordenaci?n de los elementos de un vector

 * @author Robert Sedgewick and Kevin Wayne

 */

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;

        }

}