반응형 알고리즘/기본 알고리즘5 [Java][알고리즘][정렬] Quick Sort / 퀵 정렬 퀵 정렬 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우는 O(N^2) 이지만 실제로 수행해보면 합병 정렬보다 더 좋은 성능을 낸다. pivot을 기준으로 pivot보다 작은 원소들은 pivot의 왼쪽, 큰 원소들은 오른쪽에 위치 시켜 분할 한 후, 새롭게 pivot을 만들어 재귀적으로 정렬하는 알고리즘이다. 위 예시를 보면서 이해해보도록 하자. 일반적으로는 맨 왼쪽 원소를 pivot으로 정한다. pivot을 중간값으로 잘 정하는게 퀵 정렬에서의 성능을 좌우한다. 이를 위해 3개의 원소를 정해서 중간값을 pivot으로 하는 Median of Three나 9개의 원소를 뽑아 3개씩 나눠 각 중간값을 구하고 다시 그 3개 중에서 중간값을 정해 pivot으로 정하기도 하지만.. 맨 왼쪽으로 그냥 하도록 하자.. 2019. 6. 19. [Java][알고리즘][정렬] Merge Sort / 합병 정렬 합병 정렬 분할 정복 방식을 이용한 정렬이다. 드디어 성능이 좋아진다! O(NlogN)을 보장해준다. 각 배열을 계속 분할하여 정렬을 시키고 다시 합치면서 다시 정렬을 해준다. Merge에서는 위와 같은 과정이 생긴다. 단점으로는 보조 배열을 만들어야 해서 정렬하고자 하는 배열과 같은 크기의 보조 배열을 만들어줘야 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 public class Merge { public static boolean isless(Comparable a, Comparabl.. 2019. 6. 18. [Java][알고리즘][정렬] Insertion Sort / 삽입 정렬 삽입 정렬 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 '삽입' 하는 것이다. 어느 정도 정렬이 되있는 상태의 배열에서는 좋은 성능을 낼 수 있다. 하지만 만약 역으로 정렬된 경우라면 선택, 버블 정렬과 같은 성능이 나온다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public class Insertion { public static boolean isless(Comparable a, Comparable b) { return a.compareTo(b) 2019. 6. 17. [Java][알고리즘][정렬] Bubble Sort / 버블 정렬 버블 정렬 이웃한 원소끼리 비교하여 작은 값을 앞쪽으로 보내 가장 큰 값을 정렬이 되지 않는 부분 중 가장 뒤로 보내는 것이다! 선택 정렬과 더불어 가장 간단한 정렬이다. 시간 복잡도는 O(N^2) 이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public class Bubble { public static void Sort(Comparable[] arr) { for(int i=arr.length-1; i>0; i--) { for(int j=0; j 2019. 6. 16. 이전 1 2 다음 반응형
