반응형 정렬5 [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. [Java][알고리즘][정렬] Selection Sort / 선택 정렬 정렬에 대해서 쭉 포스팅을 시작하겠다! 선택 정렬 선택정렬은 배열에서 아직 정렬되지 않은 부분의 원소 중에서 최솟값을 찾아 정렬된 부분의 바로 오른쪽 원소와 교환하는 알고리즘이다. 따라서 for문을 돌면서 min을 i번째로 설정하고 정렬이 안된 부분에서 최솟값을 찾아 교환해주면 된다. 모든 요소에 대해 i를 정하고 정렬 안된 부분이 하나씩 줄어들면서 계속 비교하므로 시간 복잡도는 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 32 33 public class Selection { public stat.. 2019. 6. 4. 이전 1 2 다음 반응형
