From 67393f42f41ab92219deb549f711121c4dab845b Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sun, 15 Dec 2019 10:34:58 +0700 Subject: [usth/ICT2.2] Object Oriented Programming --- usth/ICT2.2/midterm/src/Compare.java | 9 ++++++ usth/ICT2.2/midterm/src/Heap.java | 61 ++++++++++++++++++++++++++++++++++++ usth/ICT2.2/midterm/src/Person.java | 38 ++++++++++++++++++++++ usth/ICT2.2/midterm/src/Search.java | 57 +++++++++++++++++++++++++++++++++ usth/ICT2.2/midterm/src/Sort.java | 49 +++++++++++++++++++++++++++++ 5 files changed, 214 insertions(+) create mode 100644 usth/ICT2.2/midterm/src/Compare.java create mode 100644 usth/ICT2.2/midterm/src/Heap.java create mode 100644 usth/ICT2.2/midterm/src/Person.java create mode 100644 usth/ICT2.2/midterm/src/Search.java create mode 100644 usth/ICT2.2/midterm/src/Sort.java (limited to 'usth/ICT2.2/midterm/src') 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> implements Comparator +{ + 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 +{ + private List list; + private Comparator 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 a, Comparator 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 +{ + 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 + int binary(List> 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 + int binary(List> list, T key) + { + return binary(list, key, 0, list.size()); + } + + private static + int binary(List list, T key, Comparator 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 + int binary(List list, T key, Comparator 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 void selection(List list, Comparator 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 > void selection(List list) + { + selection(list, new Compare()); + } + + public static void bubble(List list, Comparator 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 > void bubble(List list) + { + bubble(list, new Compare()); + } + + public static void heap(List list, Comparator comparator) + { + var heap = new Heap(list, comparator); + for (int i = 1; i < list.size(); ++i) + heap.pop(); + } + + public static > void heap(List list) + { + heap(list, new Compare()); + } +} -- cgit 1.4.1