1

이번 포스트에서는 요소를 역정렬 하는 방법에 대해서 살펴보자. Comparator.reverseOrder() 객체형 배열의 역정렬 객체형 배열을 역정렬하기 위해서는 Comparator가 자기는 static 메서드인 reverseOrder를 사용하면 간단히 해결할 수 있다. public static

1. API를 이용한 정렬 처리 앞서 다양한 정렬 알고리즘을 배웠지만 막상 코드를 작성할 때 긴 정렬 알고리즘을 작성하고 있기에는 시간도 부족하고 아무래도 실수도 많이 발생하게 된다. 따라서 대부분의 언어에서는 미리 잘 작성된 정렬 알고리즘을 가지고 정렬을 처리할 수 있게 지원한다. 자바 역시 마찬가지이다. 자바에서는 배열의 경우 Arrays, Collection의 경우 Collections에서 관련 기능을 제공하는데 사용법은 거의 동일하다. 2. Arrays.sort(T[]) 가장 먼저 Arrays.sort(T[]) 형태의 메서드를 살펴보자. 다음은 int []을 정렬하기 위한 Arrays의 소스이다. public static void sort(int[] a) { DualPivotQuicksort.so..

1. 기본 컨셉 - 병합 정렬과 마찬가지로 분할/정복 알고리즘에 기반한 정렬 방식 - 요소를 분할할 원소인 pivot을 선정 - pivot보다 작은 값은 왼쪽, pivot보다 큰 값은 오른쪽에 오도록 재배치해서 분할 - 분할된 두 개의 리스트에 대해 재귀 함수를 통해 과정 반복 - 시간 복잡도는 worst case가 O(n^2), 평균 O(nlogn)인데 무려 퀵 정렬이라니!! 왜일까? - https://www.youtube.com/watch?v=ywWBy6J5gz8 2. 정렬 과정 퀵소트의 과정은 피봇을 이용해서 요소를 두 개로 그룹으로 나누는 파티셔닝 과정과 두 개의 그룹을 각각 다시 정렬하는 재귀 형태로 쪼개서 살펴볼 수 있다. int [] src = {4,2,8,6,0,5,1,7,3,9}를 정렬시..

1. 기본 컨셉 - 분할/정복(divide and conquer) 알고리즘에 기반한 정렬 방식 - 요소들이 하나가 될 때까지 분할했다가 분할된 요소들을 크기에 따라서 정렬하는 방식 - 분할된 요소들이 그룹별로 정렬 된 후 다시 이전 요소와 비교해서 병합하는 방식 - https://www.youtube.com/watch?reload=9&v=XaqR3G_NVoo 2. 정렬 과정 - 병합 정렬을 다음과 같이 재귀 함수 형태를 사용한다. private void mergeSort(int[] arr, int si, int ei) { if (si < ei) { // 요소의 길이가 2개 이상일 때까지 계속해서 진행 int mi = (si + ei) / 2; // 중간 위치를 계산해서 배열 균등 분할 - Divide m..

Counting Sort(계수 정렬) 1. 기본 컨셉 요소를 인덱스로 하는 배열에 요소들의 등장 회수를 세어서 저장한 후 정렬에 사용한다. 2. 정렬 과정 다음의 배열 요소를 정렬해보자. int [] src = {3,5,7,10,3,10}} 요소의 등장회수를 저장할 배열 생성: 여기서는 10이 가장 크기 때문에 배열의 크기가 11인 count 배열이 필요하다. count에 각 배열 요소의 등장 회수를 저장한다. 다음으로 요소들의 위치를 잡기 위해 data 를 누적해준다. 이제 뒤에서 부터 등장회수 즉 data가 0보다 큰 경우 index에 해당하는 요소들을 누적 데이터에 의해 배치해준다. 단 인덱스를 표현해야 하므로 -1 해주는 것을 잊지 말자. 또한 배치 이후 data와 누적 data를 모두 -1 처리..