반응형 Tech/알고리즘7 퀵 정렬(Quick Sort) - 퀵 정렬 public class QuicSort { public static void quickSort(int[] arr, int left, int right) { int i, j, pivot, tmp; if (left pivot) j--; // pivot 보다 작은값의 index을 찾는다. // 이 부분에서 arr.. 2020. 6. 2. 삽입 정렬(Insertion Sort) - 삽입 정렬 비교할 값을 key로 잡고 앞쪽 부터 key값과 비교하여 key 값이 위치할 index에 값을 입력한다. 선택 정렬이나 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠르다. public class InsertionSort { /** * 뒤 쪽 부터 시작하여 앞에 값들을 비교한다. * @param arr */ public static void insertionSort(int[] arr) { for(int index = 1 ; index < arr.length ; index++){ int temp = arr[index]; // 비교할 key값 int aux = index - 1; // 비교될 첫번쨰 index // 비교할 index 가 없을때 까지 && 비교할 key 값이 작을때까지 계속.. 2020. 6. 1. 선택정렬(SelectionSort) - 선택 정렬 검색 범위에서 가장 작은 값을 찾아 왼쪽으로 이동시키는 정렬 방법이다. 버블 정렬 처럼 2중 for 문을 사용하기 때문에 시간 복잡도는 O(n^2)이며 그렇기 때문에 계산하는 시간이 느리다. 선택 정렬은 시간복잡도는 버블 정렬과 동일하지만 버블 정렬보다 성능이 좋다(조금) public class SelectionSort { public static void selectionSort(int[] list) { int indexMin, temp; for (int i = 0; i < list.length - 1; i++) { indexMin = i;// 범위중 가장 작은값 index for (int j = i + 1; j < list.length; j++) { if (list[j] < list[i.. 2020. 6. 1. 버블정렬 (BubbleSort) - 버블정렬(BubbleSort) 가장 기본인 정렬 방법 중 하나이다. 인접한 값을 비교하여 정렬하는 방법이다. 2중 for 문을 사용하기 때문에 시간 복잡도는 O(n^2)이며 그렇기 때문에 계산하는 시간이 느리다. public class BubbleSort { public static void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i < arr.length; i++) { for(int j= 1 ; j < arr.length-i; j++) { if(arr[j] 2020. 6. 1. 2진 탐색 트리 알고리즘 (Binary Search Tree) - 용어 정리 노드(node) : 네트워크에서 연결 포인트 혹은 데이터 전송의 종점, 재분배점 등을 의미한다. 루트(Root) : 2진트리를 구성하는 최상위 노드 브랜치(Branch) : 노드와 노드를 연결 하는 선 레벨(Level) : 트리의 깊이를 의미한다. 서브 트리(SubTree) : 트리를 구성하는 트리(트리안에 있는 다른 트리) - 2진 탐색 트리 자식 노드가 최대 2개를 가질 수 있다. 왼쪽 자식 노드는 부모 노드보다 값이 작다. 외른쪽 자식 노드는 부모 노드보다 값이 크다. 입력 : 35 -> 18 -> 68 -> 7 -> 3 -> 12 ... 1. 35입력 비교할 부모 Node 값 없으무로 Root Node입니다. 2. 18 이 들어오고 부모노드인 35 와 비교 합니다. 작으면 왼쪽 크면.. 2020. 5. 26. 2진 탐색 알고리즘 (Binary Search Algorithm) - 2진 탐색 알고리즘 (Binary Search Algorithm) 2진 트리 알고리즘은 값이 정렬되어 있을 때 사용 가능한 검색 알고리즘 입니다. 순차(선형) 검색 알고리즘과 달리 리스트 앞부터 순차적으로 값을 찾는 방법이 아니무로 리스트가 길이가 길수록 순차 검색 알고리즘보다 빨리 검색 할 수 있습니다. 위 그림을 보면서 설명 하도록 하겠습니다. 리스트 길이는 10이고 그 중 정수 17을 찾는 방법입니다. 1. 찾고자 하는 범위에 중간의 Index 값(11)을 확인 합니다. -----> 2번째 List 그림 2. 1번에서 찾은 값(11)이 찾고자하는 값(17)이 아닐경우 1번에서 찾은 값(11)과 찾고자하는 값이(17) 비교하여 찾는 값이 크면 왼쪽의 범위를 배제하고, 작을 경우 오른쪽 범위를 배제.. 2020. 5. 26. 이전 1 2 다음 반응형
