svn-gvsig-desktop / tags / v1_0_2_Build_896 / libraries / libCq CMS for java.old / src / org / cresques / filter / QuickSort.java @ 10391
History | View | Annotate | Download (2.5 KB)
1 | 5978 | nacho | /*
|
---|---|---|---|
2 | * Cresques Mapping Suite. Graphic Library for constructing mapping applications.
|
||
3 | *
|
||
4 | * Copyright (C) 2004-5.
|
||
5 | *
|
||
6 | * This program is free software; you can redistribute it and/or
|
||
7 | * modify it under the terms of the GNU General Public License
|
||
8 | * as published by the Free Software Foundation; either version 2
|
||
9 | * of the License, or (at your option) any later version.
|
||
10 | *
|
||
11 | * This program is distributed in the hope that it will be useful,
|
||
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
14 | * GNU General Public License for more details.
|
||
15 | *
|
||
16 | * You should have received a copy of the GNU General Public License
|
||
17 | * along with this program; if not, write to the Free Software
|
||
18 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,USA.
|
||
19 | *
|
||
20 | * For more information, contact:
|
||
21 | *
|
||
22 | * cresques@gmail.com
|
||
23 | */
|
||
24 | package org.cresques.filter; |
||
25 | |||
26 | |||
27 | /**
|
||
28 | * Ordenaci?n de los elementos de un vector
|
||
29 | * @author Robert Sedgewick and Kevin Wayne
|
||
30 | */
|
||
31 | public class QuickSort { |
||
32 | private long comparisons = 0; |
||
33 | private long exchanges = 0; |
||
34 | |||
35 | /***********************************************************************
|
||
36 | * Quicksort code from Sedgewick 7.1, 7.2.
|
||
37 | ***********************************************************************/
|
||
38 | public void quicksort(int[] a) { |
||
39 | quicksort(a, 0, a.length - 1); |
||
40 | } |
||
41 | |||
42 | public void quicksort(int[] a, int left, int right) { |
||
43 | if (right <= left) {
|
||
44 | return;
|
||
45 | } |
||
46 | |||
47 | int i = partition(a, left, right);
|
||
48 | quicksort(a, left, i - 1);
|
||
49 | quicksort(a, i + 1, right);
|
||
50 | } |
||
51 | |||
52 | private int partition(int[] a, int left, int right) { |
||
53 | int i = left - 1; |
||
54 | int j = right;
|
||
55 | |||
56 | while (true) { |
||
57 | // find item on left to swap
|
||
58 | while (less(a[++i], a[right]))
|
||
59 | ; |
||
60 | |||
61 | // find item on right to swap
|
||
62 | while (less(a[right], a[--j]))
|
||
63 | |||
64 | if (j == left) {
|
||
65 | break;
|
||
66 | } |
||
67 | |||
68 | // check if pointers cross
|
||
69 | if (i >= j) {
|
||
70 | break;
|
||
71 | } |
||
72 | |||
73 | exch(a, i, j); |
||
74 | } |
||
75 | |||
76 | // swap with partition element
|
||
77 | exch(a, i, right); |
||
78 | |||
79 | return i;
|
||
80 | } |
||
81 | |||
82 | // is x < y ?
|
||
83 | private boolean less(int x, int y) { |
||
84 | comparisons++; |
||
85 | |||
86 | return (x < y);
|
||
87 | } |
||
88 | |||
89 | // exchange a[i] and a[j]
|
||
90 | private void exch(int[] a, int i, int j) { |
||
91 | exchanges++; |
||
92 | |||
93 | int swap = a[i];
|
||
94 | a[i] = a[j]; |
||
95 | a[j] = swap; |
||
96 | } |
||
97 | } |