001 /*
002 * LAPIS lightweight structured text processing system
003 *
004 * Copyright (C) 1998-2002 Carnegie Mellon University,
005 * Copyright (C) 2003 Massachusetts Institute of Technology.
006 * All rights reserved.
007 *
008 * This library is free software; you can redistribute it
009 * and/or modify it under the terms of the GNU General
010 * Public License as published by the Free Software
011 * Foundation, version 2.
012 *
013 * LAPIS homepage: http://graphics.lcs.mit.edu/lapis/
014 */
015
016 package lapisx.sort;
017
018 import java.util.Random;
019
020 public abstract class Quicksort {
021 private static Random random = new Random ();
022
023
024 //
025 // sorting collections of objects
026 //
027
028 public static void sort (Sortable a) {
029 sort (a, 0, a.size()-1);
030 }
031
032 public static void sort (Sortable a, int p, int r) {
033 if (p < r) {
034 int q = partition (a, p, r);
035 sort (a, p, q);
036 sort (a, q+1, r);
037 }
038 }
039
040 private static int partition (Sortable a, int p, int r) {
041 Object x = a.get (p + Math.abs (random.nextInt () % (r-p+1)));
042 int i = p-1;
043 int j = r+1;
044 while (true) {
045 do j = j-1;
046 while (a.compare (a.get (j), x) > 0);
047 do i = i+1;
048 while (a.compare (a.get (i), x) < 0);
049 if (i < j)
050 a.swap (i, j);
051 else return j;
052 }
053 }
054
055 //
056 // sorting collections of non-objects
057 //
058
059 public static void sort (Sortable2 a) {
060 sort (a, 0, a.size()-1);
061 }
062
063 public static void sort (Sortable2 a, int p, int r) {
064 if (p < r) {
065 int q = partition (a, p, r);
066 sort (a, p, q);
067 sort (a, q+1, r);
068 }
069 }
070
071 private static int partition (Sortable2 a, int p, int r) {
072 int x = p + Math.abs (random.nextInt () % (r-p+1));
073 int i = p-1;
074 int j = r+1;
075
076 while (true) {
077 do j = j-1;
078 while (a.compare (j, x) > 0);
079 do i = i+1;
080 while (a.compare (i, x) < 0);
081 if (i < j) {
082 a.swap (i, j);
083 if (x == i)
084 x = j;
085 else if (x == j)
086 x = i;
087 } else return j;
088 }
089 }
090
091
092 //
093 // sorting linked lists
094 //
095
096 public static SortableList sort (SortableList l, int n) {
097 return sort (l, n, null);
098 }
099
100 public static SortableList sort (SortableList l) {
101 int n = 0;
102 for (SortableList p = l; p != null; p = p.next ())
103 ++n;
104 return sort (l, n);
105 }
106
107 private static SortableList sort (SortableList l, int n, SortableList tail) {
108 if (l == null)
109 return tail;
110
111 SortableList headLT = null, tailLT = null;
112 SortableList headGT = null, tailGT = null;
113 SortableList headEQ = null, tailEQ = null;
114 int nLT = 0, nGT = 0;
115 int pivotIndex = random.nextInt () % n;
116 SortableList pivot = traverse (l, pivotIndex);
117 while (l != null) {
118 int c = l.compareTo (pivot);
119 if (c == 0) {
120 if (tailEQ == null)
121 headEQ = tailEQ = l;
122 else {
123 tailEQ.setNext (l);
124 tailEQ = l;
125 }
126 }
127 else if (c < 0) {
128 ++nLT;
129 if (tailLT == null)
130 headLT = tailLT = l;
131 else {
132 tailLT.setNext (l);
133 tailLT = l;
134 }
135 }
136 else {
137 ++nGT;
138 if (tailGT == null)
139 headGT = tailGT = l;
140 else {
141 tailGT.setNext (l);
142 tailGT = l;
143 }
144 }
145
146 SortableList next = l.next ();
147 l.setNext (null);
148 l = next;
149 }
150
151 if (headEQ == null)
152 return sort (headLT, nLT, sort (headGT, nGT, tail));
153 else {
154 tailEQ.setNext (sort (headGT, nGT, tail));
155 return sort (headLT, nLT, headEQ);
156 }
157 }
158
159 private static SortableList traverse (SortableList l, int n) {
160 while (n > 0) {
161 l = l.next ();
162 --n;
163 }
164 return l;
165 }
166
167
168 }