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.filter;

/**

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

    }

}