Algoritms (10) 썸네일형 리스트형 Selection Sort in Java Time complexity 1. Worst Case: O(N^2) 2. Best Case: O(N^2) public static void sort(Comparable[] a) { int n = a.length; for (int i = 0; i < n; i++) { int min = i; for (int j = i+1; j < n; j++) { if (less(a[j], a[min])) min = j; } exch(a, i, min); assert isSorted(a, 0, i); } assert isSorted(a); } // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } /.. QuickSort public static List quickSort(List numbers) { if (numbers.size() < 2) { return numbers; } final Integer pivot = numbers.get(0); final List lower = new ArrayList(); final 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)); } } final List sorted = quickSort(lower); sorted.add(pivot); .. MergeSort public static List mergeSort(final List numbers) { if (numbers.size() < 2) { return numbers; } final List leftHalf = numbers.subList(0, numbers.size() / 2); final List rightHalf = numbers.subList(numbers.size() / 2, numbers.size()); return merge(mergeSort(leftHalf), mergeSort(rightHalf)); } private static List merge(final List left, final List right) { int leftPtr = 0; int rightPtr = 0; final Li.. InsertSort Time complexity 1. Worst Case: O(N^2) 2. Best Case: O(N) /* programming interview exposed */ public static List InsertSort_1(final 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(), n.. BubbleSort Time complexity 1. Worst Case: O(N^2) 2. Best Case: O(N) public void bubbleSort(int[] intArray) { boolean numberSwitched; int temp; do { numberSwitched = false; for (int i = 0; i intArray[i+1]) { temp = intArray[i+1]; intArray[i+1] = intArray[i]; intArray[i] = temp; numberSwitched = true; } } } while (numberSwitched); } BinarySearch in Java public static boolean binarySearch(final List numbers, final Integer value) { if (numbers == null || numbers.isEmpty()) { System.out.println("numbers is null or empty !"); return false; } final 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 bin.. Binary Serach in C and Python Binary search is one of the fundamental algorithms in computer science. In order to explore it, we’ll first build up a theoretical backbone, then use that to implement the algorithm properly. Finding a value in a sorted sequence In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now). We’ll call the sought value the.. Two Sum Problem Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution. [Example] Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. Codes in Java/** * @author Heeyeon.nah * */public class TwoSum {public static void main(String[] args) { int[] input = { 2,.. 이전 1 2 다음