From f3018be7da2a80e635bfc78b8f8f3e58877cce29 Mon Sep 17 00:00:00 2001 From: jprocter Date: Tue, 9 Feb 2010 17:30:00 +0000 Subject: [PATCH] qsort objects on integers --- src/jalview/util/QuickSort.java | 50 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 50 insertions(+) diff --git a/src/jalview/util/QuickSort.java b/src/jalview/util/QuickSort.java index a482fef..c28928d 100755 --- a/src/jalview/util/QuickSort.java +++ b/src/jalview/util/QuickSort.java @@ -20,6 +20,10 @@ package jalview.util; public class QuickSort { + public static void sort(int[] arr, Object[] s) + { + sort(arr, 0, arr.length - 1, s); + } public static void sort(float[] arr, Object[] s) { sort(arr, 0, arr.length - 1, s); @@ -70,6 +74,17 @@ public class QuickSort sort(arr, q + 1, r, s); } } + public static void sort(int[] arr, int p, int r, Object[] s) + { + int q; + + if (p < r) + { + q = partition(arr, p, r, s); + sort(arr, p, q, s); + sort(arr, q + 1, r, s); + } + } private static int partition(float[] arr, int p, int r, Object[] s) { @@ -105,6 +120,41 @@ public class QuickSort } } } + + private static int partition(int[] arr, int p, int r, Object[] s) + { + int x = arr[p]; + int i = p - 1; + int j = r + 1; + + while (true) + { + do + { + j = j - 1; + } while (arr[j] > x); + + do + { + i = i + 1; + } while (arr[i] < x); + + if (i < j) + { + int tmp = arr[i]; + arr[i] = arr[j]; + arr[j] = tmp; + + Object tmp2 = s[i]; + s[i] = s[j]; + s[j] = tmp2; + } + else + { + return j; + } + } + } private static int partition(double[] arr, int p, int r, Object[] s) { -- 1.7.10.2