Algoritms/Sorting (5) 썸네일형 리스트형 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); } 이전 1 다음