diff options
author | Nguyễn Gia Phong <vn.mcsinyx@gmail.com> | 2019-12-15 10:34:58 +0700 |
---|---|---|
committer | Nguyễn Gia Phong <vn.mcsinyx@gmail.com> | 2019-12-15 15:00:00 +0700 |
commit | 67393f42f41ab92219deb549f711121c4dab845b (patch) | |
tree | ebd0eb6c8a3d3bd69937312179aeaf273ea29c80 /usth/ICT2.2/midterm/src | |
parent | b38d9929f7a015b56b847fde7e83f814f354497e (diff) | |
download | cp-67393f42f41ab92219deb549f711121c4dab845b.tar.gz |
[usth/ICT2.2] Object Oriented Programming
Diffstat (limited to 'usth/ICT2.2/midterm/src')
-rw-r--r-- | usth/ICT2.2/midterm/src/Compare.java | 9 | ||||
-rw-r--r-- | usth/ICT2.2/midterm/src/Heap.java | 61 | ||||
-rw-r--r-- | usth/ICT2.2/midterm/src/Person.java | 38 | ||||
-rw-r--r-- | usth/ICT2.2/midterm/src/Search.java | 57 | ||||
-rw-r--r-- | usth/ICT2.2/midterm/src/Sort.java | 49 |
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>()); + } +} |