<![CDATA[
CSE143 Program Example handout #19
Program file Sorter.java
------------------------
// This program has a method sort that can sort a LinkedList of Strings. It
// uses a mergesort algorithm. Method main tests it by constructing two
// LinkedLists of Strings. It compares the time used by this sort versus
// the standard Collections.sort.
import java.util.*;
public class Sorter {
public static void main(String[] args) {
int n = 100000;
LinkedList<String> list1 = new LinkedList<String>();
LinkedList<String> list2 = new LinkedList<String>();
Random r = new Random();
for (int i = 0; i < n; i++) {
String text = "some text with #" + r.nextInt(2 * n);
list1.add(text);
list2.add(text);
}
long start = System.currentTimeMillis();
sort(list1);
double elapsed1 = (System.currentTimeMillis() - start)/1000.0;
System.out.println("linked list sort took " + elapsed1 + " seconds");
System.out.println();
start = System.currentTimeMillis();
Collections.sort(list2);
double elapsed2 = (System.currentTimeMillis() - start)/1000.0;
System.out.println("collections sort took " + elapsed2 + " seconds");
System.out.println();
System.out.println("Ratio = " + elapsed1 / elapsed2);
Iterator<String> i1 = list1.iterator();
Iterator<String> i2 = list2.iterator();
boolean match = true;
while (match && i1.hasNext() && i2.hasNext())
if (i1.next() != i2.next())
match = false;
if (!match || i1.hasNext() || i2.hasNext())
System.out.println("lists don't match");
}
// post: list is in sorted (nondecreasing) order
public static void sort(Queue<String> list) {
if (list.size() > 1) {
Queue<String> half1 = new LinkedList<String>();
Queue<String> half2 = new LinkedList<String>();
int size1 = list.size() / 2;
int size2 = list.size() - size1;
for (int i = 0; i < size1; i++)
half1.add(list.remove());
for (int i = 0; i < size2; i++)
half2.add(list.remove());
sort(half1);
sort(half2);
mergeInto(list, half1, half2);
}
}
// pre : result is empty; list1 is sorted; list2 is sorted
// post: result contains the result of merging the sorted lists;
// list1 is empty; list2 is empty
public static void mergeInto(Queue<String> result,
Queue<String> list1,
Queue<String> list2) {
while (!list1.isEmpty() && !list2.isEmpty()) {
if (list1.peek().compareTo(list2.peek()) <= 0)
result.add(list1.remove());
else
result.add(list2.remove());
}
while (!list1.isEmpty())
result.add(list1.remove());
while (!list2.isEmpty())
result.add(list2.remove());
}
Sample Execution on Linux Time-Sharing System (with input increased tenfold)
----------------------------------------------------------------------------
linked list sort took 5.155 seconds
collections sort took 2.713 seconds
Ratio = 1.9001105786951715
Sample Execution on Macintosh PowerBook G4
-------------------------------------------
linked list sort took 2.405 seconds
collections sort took 0.547 seconds
Ratio = 4.39670932358318
Sample Execution on Dell Pentium-4 with Windows XP
--------------------------------------------------
linked list sort took 1.013 seconds
collections sort took 0.421 seconds
Ratio = 2.4061757719714962
]]>