ALG ppt

Size: px

Start display at page:

Download "ALG ppt"

あゆみえんの
4 years ago
Views:

2012 7 5 (sakai.keiichi@kochi-tech.ac.jp) http://www.

1 (sakai.keiichi@kochi-tech.ac.jp)

2 (198 ) f(p) p f 2

4 (, 201 ) (2 ) n/2 ( log 2 n, n) n log 2 n n/2 + n log 2 n O(n logn) 4

5 public class StraightMergeSort { private final static <E extends Comparable<E>> int merge(int seqsize, E[] from, E[] into){ int n = 0; for(int start = 0; start < from.length;){ int i = start; int j = start + seqsize; int iend = Math.min(start + seqsize, from.length); int jend = Math.min(start + 2*seqsize, from.length); while((i < iend) && (j < jend)){ n++; into[start++] = (from[i].compareto(from[j]) <= 0)? from[i++]: from[j++]; while(i < iend) into[start++] = from[i++]; while(j < jend) into[start++] = from[j++]; return n; O(n) public static <E extends Comparable<E>> int sort(e[] array) { E[] work = (E[])Array.newInstance(array.getClass().getComponentType(), array.length); int n = 0; for(int seqsize = 1; seqsize <= array.length; seqsize *= 4){ n += merge(seqsize, array, work); n += merge(seqsize*2, work, array); return n; 2 5

6 private final static String[] test_data_string = { " ", " ", " ", " ", " ", " ", " ; private final static Integer[] test_data_int = { 47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10 ; public static void main(string[] args) { int n; StringBuffer sb = new StringBuffer(); String[] data1 = test_data_string.clone(); n = sort(data1); for (String e : data1) { sb.append(e).append(", "); sb.append("\ncompareto() ").append(n).append('\n'); Integer[] data2 = test_data_int.clone(); n = sort(data2); for (Integer e : data2) { sb.append(e).append(", "); sb.append("\ncompareto() ").append(n).append('\n'); System.out.print(sb.toString()); 6

7 (162 ) 7

8 bin = :

10 1. 0 max public class CountSort { public static <E extends Number> void sort(e[] array, int max) { int[] count = new int[max + 1]; E[] original = array.clone(); for(e e: original){ count[e.intvalue()]++; // for(int i = 1; i < count.length; i++){ count[i] += count[i-1]; // for(e e: original){ int j = --count[e.intvalue()]; array[j] = e; 10

11 public class BinSort { public static <E extends Number> void sort(e[] array, int max) { List<E>[] bin = new List[max + 1]; for(e e: array){ if(bin[e.intvalue()] == null){ bin[e.intvalue()] = new LinkedList<E>(); bin[e.intvalue()].add(e); int i = 0; for(list<e> l: bin){ if(l!= null){ for(e e: l){ array[i++] = e; 11

12 private final static Double[] test_data_double = { 47.0, 18.1, 8.2, 7.3, 2.4, 4.5, 9.6, 0.7, 72.8, 88.9, 2.0, 5.1, 9.2, 10.3, ; private final static Integer[] test_data_int = { 47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10, ; public static void main(string[] args) { StringBuffer sb = new StringBuffer(); Double[] data1 = test_data_double.clone(); sort(data1, 88); for (Double e : data1) sb.append(e).append(", "); sb.append('\n'); Integer[] data2 = test_data_int.clone(); sort(data2, 88); for (Integer e : data2) sb.append(e).append(", "); sb.append('\n'); System.out.print(sb.toString()); 12

13 218 x y x [ 0] < y[0] x [ 0] = y[0] x[1] < y[1] x[ 0] = y[0] x[1] = y[1] x[ k 2] = y[ k 2] x[ k 1] < y[ k 1] Java 13

14 public class RadixSort { public static <E extends CharSequence> void sort(e[] array, int k) { List<E>[] bin = new List[Character.MAX_VALUE + 1]; while(--k >= 0){ for(e e: array){ int index = 0; if(k < e.length()){ index = e.charat(k); if(bin[index] == null){ bin[index] = new LinkedList<E>(); bin[index].add(e); int i = 0; for(list<e> l: bin){ if(l!= null){ for(e e: l){ array[i++] = e; l.clear(); PC 640KB 64K Java C C89 14

15 private final static String[] test_data_prefecture = { " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", ; private final static String[] test_data_direction = { " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", ; public static void main(string[] args) { StringBuffer sb = new StringBuffer(); String[] data; data = test_data_prefecture.clone(); sort(data, 4); // 4 for (String e : data) sb.append(e).append(", "); sb.append('\n'); data = test_data_direction.clone(); sort(data, 4); // 4 for (String e : data) sb.append(e).append(", "); System.out.println(sb.toString()); 15

16 16

ALG ppt

ALG ppt 2012 6 21 (sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2012/index.html 1 l l O(1) l l l 2 (123 ) l l l l () l H(k) = k mod n (k:, n: ) l l 3 4 public class MyHashtable