Do.

 이번 Posting에서는 n의 크기를 갖는 배열에서 k 번째로 작은 값을 찾는 방법에 대하여 이야기를 진행할 것입니다.   물론 가장 간단한 방법은 sorting을 진행하고 k번째 인덱스에 접근하면 끝입니다. 그렇다면 가장 성능이 좋은 녀석은 무엇일까요? 일단 2가지 경우만 생각하도록 하겠습니다. 시간 복잡도가 nlogn이고, 공간 복잡도가 n인 in-place sorting만 생각을 하면 quick sort, heap sort로 한정이 되겠지요. 다시 이문제를 "selection" 문제라고 하자!! Selection  이 문제를 풀어내는 방법에는 여러가지가 있다, 물론 Sorting 보다 빠른 방법으로 해야 이 문제를 푸는 의미가 있을 것이다. Quick sort 토너먼트 Selection sort Approximate Median Quick Sort  Quick sort를 K 근처에서 수행한다면 어떻게 될까? 최선의 경우 O(n)에 끝나지만, 최악의 경우O(n^2)이 걸리고 평균적으로는 O(n)이 된다. 토너먼트  토너먼트 방식을 사용하면 1등은 n, 2등은 n + logn, 3등은 n + 2logn, ..., k등은 n + klogn 이 걸리게 된다. Selection Sort  selection sort를 k번째까지 수행한다면 kn 시간이 걸리고 만약에 k가 n/2이면 O(n^2)이 걸리게 된다. Approximate Median  정의는 rn등부터 (1-r)n등 사이의 원소. (단 0 < r < 1). - r = 0.3이라고 가정. 알고리즘은 다음과 같다. 배열을 5개로 분할하고, 각 분할의 중간 값을 찾아냅니다.  이 후 중간 값들 중 실제 중간 값을 찾습니다. 결론적으로 이 실제 중간 값은 반드시 rn등과 (...

이번 Posting에서는 기본적인 sorting들에 대하여 정리를 할 것이다. Bubble sort(버블 정렬) Insertion sort(삽입 정렬) Selection sort(선택 정렬) Heap sort(힙 정렬) Quick sort(퀵 정렬) merge sort(병합 정렬) 1. Bubble sort(버블 정렬)  거품 정렬은 정렬을 처음 배울 때 나오는 녀석이다. 가장 직관적이고 이해하기 쉽기 때문에 처음에 배우는 것이라고 생각한다. 이 녀석의 시간 복잡도는 O(N^2) 즉 for문 2개로 정렬을 할 수가 있다. 쉽지만 퍼포먼스가 떨어지기 때문에 잘 사용하지 않는다. 버블 정렬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class BubbleSort { static int [] data = { 14 , 6 , 45 , 43 , 41 , 28 , 38 , 36 , 49 , 16 , 34 }; public static void main (String[] args) { bubbleSort(); for ( int i = 0 ; i < data. length ; i++) { System. out . print (data[i]); if (i < data. length - 1 ) System. out . print ( " " ); } } public static void bubbleSort () { for ( int i = 0 ; i < data. length ; i++) { for ( int j = 1 ; j < data...

이번 Posting에서는 Counting sort, Radix sort, Bucket sort에 대해서 정리를 할 것이다. Counting sort  배열 내에 최댓값을 배열의 길이만큼의 새로운 버킷을 만든다.  배열의 각 값들을 인덱스로하는 버킷 배열에 그 수를 counting.  counting이 완료된 것을 작은 index부터 큰 쪽으로 누적 시킨다.  원래 배열 뒤에서부터 차례로 자리를 찾는다.  자리는 bucket에 저장된 값으로 넣어준 후 하나씩 감소시켜 같은 값이 있는 경우를 계산한다.  낮은 인덱스부터 출력을 하면 정렬된 결과를 얻을 수 있음. 코드는 다음과 같다. 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 public class CountingSort { static int [] arr = { 7 , 3 , 5 , 9 , 11 , 2 , 6 , 12 , 10 }; static int [] sorted; static int [] bucket; static int max = 0 ; public static void main (String[] args) { for ( int i = 0 ; i < arr. length ; i++) { max = Math. max (max, arr[i]); } bucket = new int [max + 1 ]; for ( int i = 0 ; i < arr. length ; i++) { bucket[arr[i]]++; } for ( int i ...