5 files changed, 214 insertions, 0 deletions
diff --git a/usth/ICT2.2/midterm/src/Compare.java b/usth/ICT2.2/midterm/src/Compare.java
new file mode 100644
index 0000000..e6bda90
--- /dev/null
+++ b/usth/ICT2.2/midterm/src/Compare.java
@@ -0,0 +1,9 @@
+import java.util.Comparator;
+
+public class Compare<T extends Comparable<? super T>> implements Comparator<T>
+{
+  public int compare(T a, T b)
+  {
+    return a.compareTo(b);
+  }
+}
diff --git a/usth/ICT2.2/midterm/src/Heap.java b/usth/ICT2.2/midterm/src/Heap.java
new file mode 100644
index 0000000..3803924
--- /dev/null
+++ b/usth/ICT2.2/midterm/src/Heap.java
@@ -0,0 +1,61 @@
+import java.util.List;
+import java.util.Comparator;
+
+import static java.util.Collections.swap;
+
+public class Heap<T>
+{
+  private List<T> list;
+  private Comparator<T> cmp;
+  private int size;
+
+  public int getSize()
+  {
+    return size;
+  }
+
+  public int getLength()
+  {
+    return list.size();
+  }
+
+  public T get(int i)
+  {
+    return list.get(i);
+  }
+
+  public void heapify(int i)
+  {
+    int right = i + 1 << 1;
+    int left = right - 1;
+    int largest = i;
+
+    if (left < size && cmp.compare(get(left), get(largest)) > 0)
+      largest = left;
+    if (right < size && cmp.compare(get(right), get(largest)) > 0)
+      largest = right;
+    if (largest != i)
+      {
+        swap(list, i, largest);
+        heapify(largest);
+      }
+  }
+
+  public Heap(List<T> a, Comparator<T> c)
+  {
+    list = a;
+    size = a.size();
+    cmp = c;
+    for (int i = size >> 1; i-- > 0;)
+      heapify(i);
+  }
+
+  public T pop() throws RuntimeException
+  {
+    if (size < 1)
+      throw new RuntimeException("heap underflow");
+    swap(list, 0, --size);
+    heapify(0);
+    return get(size);
+  }
+}
diff --git a/usth/ICT2.2/midterm/src/Person.java b/usth/ICT2.2/midterm/src/Person.java
new file mode 100644
index 0000000..045c3f4
--- /dev/null
+++ b/usth/ICT2.2/midterm/src/Person.java
@@ -0,0 +1,38 @@
+public class Person implements Comparable<Person>
+{
+  private String name;
+  private Integer age;
+  private Character gender;
+
+  public Person(String name, Integer age, Character gender)
+  {
+    this.name = name;
+    this.age = age;
+    this.gender = gender;
+  }
+
+  public int compareTo(Person other)
+  {
+    return this.name.compareTo(other.name);
+  }
+
+  public String toString()
+  {
+    return String.format("%s (%d%c)", name, age, gender);
+  }
+
+  public String getName()
+  {
+    return name;
+  }
+
+  public Integer getAge()
+  {
+    return age;
+  }
+ 
+  public Character getGender()
+  {
+    return gender;
+  }
+}
diff --git a/usth/ICT2.2/midterm/src/Search.java b/usth/ICT2.2/midterm/src/Search.java
new file mode 100644
index 0000000..efb9e45
--- /dev/null
+++ b/usth/ICT2.2/midterm/src/Search.java
@@ -0,0 +1,57 @@
+import java.util.List;
+import java.util.Comparator;
+
+public class Search
+{
+  public static final int NOT_FOUND = -1;
+
+  public static int linear(List list, Object key)
+  {
+    for (int i = 0; i < list.size(); ++i)
+      if (key == null ? list.get(i) == null : key.equals(list.get(i)))
+        return i;
+    return NOT_FOUND;
+  }
+
+  private static <T>
+  int binary(List<? extends Comparable<? super T>> list, T key,
+             int low, int high)
+  {
+    if (high < low)
+      return NOT_FOUND;
+    var mid = (low + high) / 2;
+    var cmp = list.get(mid).compareTo(key);
+    if (cmp < 0)
+      return binary(list, key, mid + 1, high);
+    if (cmp > 0)
+      return binary(list, key, low, mid - 1);
+    return mid;
+  }
+
+  public static <T>
+  int binary(List<? extends Comparable<? super T>> list, T key)
+  {
+    return binary(list, key, 0, list.size());
+  }
+
+  private static <T>
+  int binary(List<? extends T> list, T key, Comparator<? super T> c,
+             int low, int high)
+  {
+    if (high < low)
+      return NOT_FOUND;
+    var mid = (low + high) / 2;
+    var cmp = c.compare(list.get(mid), key);
+    if (cmp < 0)
+      return binary(list, key, c, mid + 1, high);
+    if (cmp > 0)
+      return binary(list, key, c, low, mid - 1);
+    return mid;
+  }
+
+  public static <T>
+  int binary(List<? extends T> list, T key, Comparator<? super T> c)
+  {
+    return binary(list, key, c, 0, list.size());
+  }
+}
diff --git a/usth/ICT2.2/midterm/src/Sort.java b/usth/ICT2.2/midterm/src/Sort.java
new file mode 100644
index 0000000..3f146af
--- /dev/null
+++ b/usth/ICT2.2/midterm/src/Sort.java
@@ -0,0 +1,49 @@
+import java.util.List;
+import java.util.Comparator;
+
+import static java.util.Collections.swap;
+
+public class Sort
+{
+  public static <T> void selection(List<T> list, Comparator<T> comparator)
+  {
+    int i, j, m, n = list.size();
+    for (i = 0; i < n; ++i)
+      {
+        for (m = j = i; j < n; ++j)
+          if (comparator.compare(list.get(j), list.get(m)) < 0)
+            m = j;
+        swap(list, i, m);
+      }
+  }
+
+  public static <T extends Comparable<? super T>> void selection(List<T> list)
+  {
+    selection(list, new Compare<T>());
+  }
+
+  public static <T> void bubble(List<T> list, Comparator<T> comparator)
+  {
+    for (int n = list.size(), m = 0; n > 1; n = m, m = 0)
+      for (int i = 1; i < n; ++i)
+        if (comparator.compare(list.get(i), list.get(i - 1)) < 0)
+          swap(list, m = i, i - 1);
+  }
+
+  public static <T extends Comparable<? super T>> void bubble(List<T> list)
+  {
+    bubble(list, new Compare<T>());
+  }
+
+  public static <T> void heap(List<T> list, Comparator<T> comparator)
+  {
+    var heap = new Heap<T>(list, comparator);
+    for (int i = 1; i < list.size(); ++i)
+      heap.pop();
+  }
+
+  public static <T extends Comparable<? super T>> void heap(List<T> list)
+  {
+    heap(list, new Compare<T>());
+  }
+}