<![CDATA[
CSE143 Program Example handout #19
Non-Generic version Sorter.java
-------------------------------
// Stuart Reges
// 11/21/05
//
// 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();
while (i1.hasNext() && i2.hasNext())
if (i1.next() != i2.next())
throw new RuntimeException("lists don't match");
}
// post: list is in sorted (nondecreasing) order
public static void sort(LinkedList<String> list) {
if (list.size() > 1) {
LinkedList<String> half1 = new LinkedList<String>();
LinkedList<String> half2 = new LinkedList<String>();
int size1 = list.size() / 2;
int size2 = list.size() - size1;
for (int i = 0; i < size1; i++)
half1.addLast(list.removeFirst());
for (int i = 0; i < size2; i++)
half2.addLast(list.removeFirst());
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(LinkedList<String> result,
LinkedList<String> list1,
LinkedList<String> list2) {
while (!list1.isEmpty() && !list2.isEmpty()) {
if (list1.getFirst().compareTo(list2.getFirst()) <= 0)
result.addLast(list1.removeFirst());
else
result.addLast(list2.removeFirst());
}
while (!list1.isEmpty())
result.addLast(list1.removeFirst());
while (!list2.isEmpty())
result.addLast(list2.removeFirst());
}
}
Generic version Sorter2.java
----------------------------
// Stuart Reges
// 11/21/05
//
// This program has a generic method sort that can sort any List<E> where E
// implements the Comparable<E> interface. It uses a mergesort algorithm with
// LinkedLists. Method main tests it by constructing two ArrayLists containing
// Strings. It compares the time used by this sort versus Collections.sort.
import java.util.*;
public class Sorter2 {
public static void main(String[] args) {
int n = 100000;
List<String> list1 = new ArrayList<String>();
List<String> list2 = new ArrayList<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();
while (i1.hasNext() && i2.hasNext())
if (i1.next() != i2.next())
throw new RuntimeException("lists don't match");
}
// pre : all elements of the list implement Comparable<E> and are mutually
// comparable
// post: list is in sorted (nondecreasing) order
public static <E> void sort(List<E> list) {
LinkedList<E> data = new LinkedList<E>(list);
list.clear();
sort(data);
list.addAll(data);
}
// pre : all elements of the list implement Comparable<E> and are mutually
// comparable
// post: list is in sorted (nondecreasing) order
public static <E> void sort(LinkedList<E> list) {
if (list.size() > 1) {
LinkedList<E> half1 = new LinkedList<E>();
LinkedList<E> half2 = new LinkedList<E>();
int size1 = list.size() / 2;
int size2 = list.size() - size1;
for (int i = 0; i < size1; i++)
half1.addLast(list.removeFirst());
for (int i = 0; i < size2; i++)
half2.addLast(list.removeFirst());
sort(half1);
sort(half2);
mergeInto(list, half1, half2);
}
}
// pre : result is empty; all elements in list1 and list2 implement
// Comparable<E> and are mutually comparable; list1 is sorted;
// list2 is sorted
// post: result contains the result of merging the sorted lists;
// list1 is empty; list2 is empty
public static <E> void mergeInto(LinkedList<E> result,
LinkedList<E> list1,
LinkedList<E> list2) {
while (!list1.isEmpty() && !list2.isEmpty()) {
Comparable<E> first = (Comparable<E>)list1.getFirst();
if (first.compareTo(list2.getFirst()) <= 0)
result.addLast(list1.removeFirst());
else
result.addLast(list2.removeFirst());
}
while (!list1.isEmpty())
result.addLast(list1.removeFirst());
while (!list2.isEmpty())
result.addLast(list2.removeFirst());
}
}
]]>