Skip to content

Commit 9eef02e

Browse files
melisabokmelisabok
committed
implement iterative quicksort
1 parent f729898 commit 9eef02e

3 files changed

Lines changed: 90 additions & 42 deletions

File tree

‎src/main/java/technology/tabula/QuickSort.java‎

Lines changed: 41 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818

1919
import java.util.Comparator;
2020
import java.util.List;
21+
import java.util.Stack;
2122

2223
/**
2324
* see http://de.wikipedia.org/wiki/Quicksort.
@@ -47,12 +48,7 @@ public int compare(Comparable object1, Comparable object2)
4748
*/
4849
public static <T> void sort(List<T> list, Comparator<T> cmp)
4950
{
50-
int size = list.size();
51-
if (size < 2)
52-
{
53-
return;
54-
}
55-
quicksort(list, cmp, 0, size - 1);
51+
quicksort(list, cmp);
5652
}
5753

5854
/**
@@ -65,15 +61,48 @@ public static <T extends Comparable> void sort(List<T> list)
6561
sort(list, (Comparator<T>) objComp);
6662
}
6763

68-
private static <T> void quicksort(List<T> list, Comparator<T> cmp, int left, int right)
64+
private static <T> void quicksort(List<T> list, Comparator<T> cmp)
6965
{
70-
if (left < right)
71-
{
72-
int splitter = split(list, cmp, left, right);
73-
quicksort(list, cmp, left, splitter - 1);
74-
quicksort(list, cmp, splitter + 1, right);
66+
Stack<Integer> stack = new Stack<Integer>();
67+
stack.push(0);
68+
stack.push(list.size());
69+
while (!stack.isEmpty()) {
70+
int right = stack.pop();
71+
int left = stack.pop();
72+
if (right - left < 2) continue;
73+
int p = left + ((right-left)/2);
74+
p = partition(list, cmp, p, left, right);
75+
76+
stack.push(p+1);
77+
stack.push(right);
78+
79+
stack.push(left);
80+
stack.push(p);
81+
7582
}
7683
}
84+
85+
private static <T> int partition(List<T> list, Comparator<T> cmp, int p, int start, int end) {
86+
int l = start;
87+
int h = end - 2;
88+
T piv = list.get(p);
89+
swap(list,p,end-1);
90+
91+
while (l < h) {
92+
if (cmp.compare(list.get(l), piv) <= 0) {
93+
l++;
94+
} else if (cmp.compare(piv, list.get(h)) <= 0) {
95+
h--;
96+
} else {
97+
swap(list,l,h);
98+
}
99+
}
100+
int idx = h;
101+
if (cmp.compare(list.get(h), piv) < 0) idx++;
102+
swap(list,end-1,idx);
103+
return idx;
104+
}
105+
77106

78107
private static <T> void swap(List<T> list, int i, int j)
79108
{
@@ -82,32 +111,4 @@ private static <T> void swap(List<T> list, int i, int j)
82111
list.set(j, tmp);
83112
}
84113

85-
private static <T> int split(List<T> list, Comparator<T> cmp, int left, int right)
86-
{
87-
int i = left;
88-
int j = right - 1;
89-
T pivot = list.get(right);
90-
do
91-
{
92-
while (cmp.compare(list.get(i), pivot) <= 0 && i < right)
93-
{
94-
++i;
95-
}
96-
while (cmp.compare(pivot, list.get(j)) <= 0 && j > left)
97-
{
98-
--j;
99-
}
100-
if (i < j)
101-
{
102-
swap(list, i, j);
103-
}
104-
105-
} while (i < j);
106-
107-
if (cmp.compare(pivot, list.get(i)) < 0)
108-
{
109-
swap(list, i, right);
110-
}
111-
return i;
112-
}
113114
}

‎src/test/java/technology/tabula/TestSpreadsheetExtractor.java‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -506,7 +506,9 @@ public void testDontStackOverflowQuicksort() throws IOException {
506506

507507
SpreadsheetExtractionAlgorithm sea = new SpreadsheetExtractionAlgorithm();
508508
List<Table> tables = (List<Table>) sea.extract(page);
509-
509+
for (int i = 1; i < tables.size(); i++) {
510+
assert(tables.get(i-1).getTop() <= tables.get(i).getTop());
511+
}
510512
}
511513

512514
}

‎src/test/java/technology/tabula/TestUtils.java‎

Lines changed: 46 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,17 @@
11
package technology.tabula;
22

3-
import static org.junit.Assert.*;
3+
import static org.junit.Assert.assertArrayEquals;
4+
import static org.junit.Assert.assertEquals;
5+
import static org.junit.Assert.assertNull;
46

57
import java.awt.geom.Point2D;
8+
import java.util.ArrayList;
69
import java.util.Arrays;
10+
import java.util.Collections;
711
import java.util.List;
812

913
import org.apache.commons.cli.ParseException;
14+
import org.junit.Before;
1015
import org.junit.Test;
1116

1217
public class TestUtils {
@@ -63,4 +68,44 @@ public void testAnotherExceptionInParsePages() throws ParseException {
6368
Utils.parsePagesOption("quuxor");
6469
}
6570

71+
@Test
72+
public void testQuickSortEmptyList() {
73+
List<Integer> numbers = new ArrayList<Integer>();
74+
QuickSort.sort(numbers);
75+
76+
assertEquals(Collections.emptyList(), numbers);
77+
}
78+
79+
@Test
80+
public void testQuickSortOneElementList() {
81+
List<Integer> numbers = Arrays.asList(5);
82+
QuickSort.sort(numbers);
83+
84+
assertEquals(Arrays.asList(5), numbers);
85+
}
86+
87+
@Test
88+
public void testQuickSortShortList() {
89+
List<Integer> numbers = Arrays.asList(4, 5, 6, 8, 7, 1, 2, 3);
90+
QuickSort.sort(numbers);
91+
92+
assertEquals(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8), numbers);
93+
}
94+
95+
@Test
96+
public void testQuickSortLongList() {
97+
98+
List<Integer> numbers = new ArrayList<Integer>();
99+
List<Integer> expectedNumbers = new ArrayList<Integer>();
100+
101+
for(int i = 0; i <= 12000; i++){
102+
numbers.add(12000 - i);
103+
expectedNumbers.add(i);
104+
}
105+
106+
QuickSort.sort(numbers);
107+
108+
assertEquals(expectedNumbers, numbers);
109+
}
110+
66111
}

0 commit comments

Comments
 (0)