알고리즘 (9) 썸네일형 리스트형 이진 검색 public static boolean binarySearch(List numbers, Integer value) { if (numbers == null ||numbers.isEmpty()) { return false; } Integer comparison = numbers.get(numbers.size() /2); if (value.equals(comparison)) { return true; } if (value < comparison) { return binarySearch(numbers.subList(0, numbers.size() / 2), value); } else { return binarySearch(numbers.subList(numbers.size() /2 + 1, numbers.siz.. 병합정렬 알고리즘 public static List mergesort(List values) { if (values.size() < 2) { return values; } List leftHalf = values.subList(0, values.size() /2); List rightHalf = values.subList(values.size() / 2, values.size()); return merge(mergesort(leftHalf), mergesort(rightHalf)); } private static List merge(List left, List right) { int leftPtr = 0; int rightPtr = 0; List merged = new ArrayList(left.size() + right.. 퀵 정렬 알고리즘 public static List quickSort(List numbers) { if (numbers.size() < 2) { return numbers; } Integer pivot = numbers.get(0); List lower = new ArrayList(); List higher = new ArrayList(); for(int i=1; i < numbers.size(); i++) { if (numbers.get(i) < pivot) { lower.add(numbers.get(i)); } else { higher.add(numbers.get(i)); } } List sorted = quickSort(lower); sorted.add(pivot); sorted.addAll(quickSort(hig.. 퀵 정렬 알고리즘 public static List quickSort(List numbers) { if (numbers.size() < 2) { return numbers; } Integer pivot = numbers.get(0); List lower = new ArrayList(); List higher = new ArrayList(); for(int i=1; i < numbers.size(); i++) { if (numbers.get(i) < pivot) { lower.add(numbers.get(i)); } else { higher.add(numbers.get(i)); } } List sorted = quickSort(lower); sorted.add(pivot); sorted.addAll(quickSort(hig.. 삽입 정렬 알고리즘 public static List insertSort(List numbers) { List sortedList = new LinkedList(); originalList: for (Integer number : numbers) { for(int i=0; i < sortedList.size(); i++) { if (number < sortedList.get(i)) { sortedList.add(i, number); continue originalList; } } sortedList.add(sortedList.size(), number); } return sortedList; } - 삽입 정렬은 새로운 리스트를 생성하고 해당 리스트를 반환- ArrayList 클래스를 사용 했다면 중간에 원소를 추가할 경우 .. 버블정렬 알고리즘 - 인접한 두 수를 비교해서 큰 수 (작은 수)를 뒤로 보내는 알고리즘public class BubbleSort { public static void main(String[] args) { int[] index = {8, 4, 7, 3, 1, 6, 5, 2}; int i, j, temp; for(i = 0; i index[j + 1]) { temp = index[j]; index[j] = index[j + 1]; index[j + 1] = temp; } } } for (i = 0; i < index.length; i++) { System.out.pri.. 리스트 정렬하기 - 자바는 정렬을 돕기 위해 Comparable과 Comparator라는 두 가지 인터페이스를 제공 Comparable과 Comparator 인터페이스 차이는 무었인가? - 두 인터페이스 모두 public으로 접근 변경자로 선언하기 때문에 모든 용도의 자료를 담을 수 있다. - Comparable 인터페이스는 자연스러운 순서로 정렬할 때 사용하고, Comparator는 원하는 대로 정렬 순서를 지정하고 싶은 곳에 사용Comparable Interface - 객체들 사이의 오름차순, 내림차순 등 일반적인 순서를 결정할 때 사용 - CompareTo 메소드가 있음 Prameter Comparable Comparator Sorting logic 소팅 로직은 어떤 오브젝트를 정렬하려면 같은 클래스에 있어야 한다.. 빅 오 표현법 살표보기 - 빅오 표현법은 알고리즘 성능이나 복잡도를 설명하는 데 일반적으로 사용하는 방법 - 빅 오 표현법은 입력 값이 바뀌었을 때 알고리즘 성능이 어떻게 바뀌는지 알려준다. - 예를 들어 가장 나쁜 성능을 가진 알고리즘을 표현하는 O(n2)는 입력 값이 2배가 되면 실행되는 시간은 4배로 늘어난다.- 알고리즘은 보통 최선(best-case), 최악(worst-case), 평균(average-case)이라는 세 종류의 복잡성 중 하나에 속한다.- 성능을 고려한 것을 알고리즘의 시간 복잡성이라 한다.- 알고리즘이 수행될 때 얼마나 많은 저장 공간이 필요한가를 의미하는 공간 복잡성 개념도 있다. - 알고리즘을 작성할 때는 시간/공간 복잡성을 함께 고려해야한다. 이전 1 2 다음