DeFacto-Standard IT

Arrays.sort()는 내부적으로 3개의 Sorting을 쓴다. 1. Insertion Sort 2. Merge Sort 3. QuickSort 예전에는 3개를 분리하여서 각각의 경우에 따로 사용을 했지만 지금은 1,2 1,3을 섞어서 사용한다. Insertion Sort와 Merge Sort를 섞은 것은 Tim Sort Insertion Sort와 QuickSort를 섞은 것은 Dual-Pivot Quick Sort라고 한다. 여기서는 Insertion Sort를 합치지않은, 오로지 Dual-Pivot Quick Sort를 다룬다. 기존의 Quick Sort는 Pivot이 한개 였지만 Dual-Pivot Quick Sort는 Pivot을 2개를 써서 Pivot 1보다 낮은 그룹 / Pivot1 ~ ..

다음은 여러 가지 정렬 방법의 이론적 성능을 비교한 것이다. 최적 정렬 방법은 정렬해야 할 레코드의 수, 크기, 타입 등에 따라 달라지므로, 정렬 방법들의 장단점을 잘 이해하여 적합한 정렬 방법을 사용할 수 있어야 한다. 정수 60000개를 각 정렬 알고리즘으로 정렬할 때 소요되는 시간을 측정한 결과이다. 빨간 글씨로 색칠되어 있는 Insertion / Merge / Quick Sort는 Arrays.sort()에서 사용하는 정렬 알고리즘이므로 중요하다 생각되어 표시. 실제로는 Tim Sort(Insertion + Merge), Dual-Pivot Quick Sort(Quick Sort 변형) 2가지를 쓰지만 기본 베이스는 3가지이다. 알고리즘 Time Complexity 실행시간 (sec) Space ..

앞의 정렬은 모두 레코드들을 비교하여 정렬하였다. 기수정렬은 레코드를 비교하지 않고 정렬하는 방법이다. 입력 데이터에 대해서 어떤 비교 연산도 하지 않고 데이터를 정렬할 수 있다. 정렬에 기초한 방법은 이라는 하한선을 깰 수 없는데 반해 기수 정렬은 이 하한을 깰 수 있는 유일한 정렬방법이다. 기수 정렬은 O(dn)의 시간 복잡도를 가지는데, 대부분 dfront = q->rear = 0; } // 공백 상태 검출 함수 int is_empty(QueueType *q) { return (q->front == q->rear); } // 포화 상태 검출 함수 int is_full(QueueType *q) { return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front); } // ..

히프는 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 최댓값이나 최솟값을 쉽게 추출할 수 있는 자료구조이다. 최소 히프와 최대 히프가 있고 정렬에서는 최소 히프를 사용하는 것이 프로그램이 더 쉽다. 최소 히프는 부모 노드의 값이 자식 노드의 값보다 작기 때문에 최소 히프의 루트 노드는 가장 작은 값이다. 이러한 특성을 이용하여 정렬할 배열을 먼저 최소 히프로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법이다. 히프는 1차원 배열로 쉽게 구현될 수 있다. 최소 히프를 만들고 숫자들을 차례대로 삽입한 다음 최솟값(root)부터 삭제하면 된다. 최소 히프는 작은 값이 root고 이것부터 뽑아 내므로 오름차순 정렬, 최대 히프는 큰 값이 root이고 이것부터 뽑아 내므로 내림차순 정렬에 ..

퀵 정렬은 평균적으로 매우 빠른 수행 속도를 보인다. 이 역시 분할 정복 방법에 근거한다. 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할한다. 각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용한다. 그러나 퀵 정렬은 리스트를 다음과 같은 방법으로 비균등하게 분할한다. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소라고 가정한다. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 결과적으로 피벗을 중심으로 왼쪽은 작은 요소들, 오른쪽은 큰 요소들로 구성된다. 이 상태에서 피벗을 제외한 왼쪽, 오른쪽 리스트를 다시 정렬하면 전체 리스트가 정렬된다. 퀵 정렬 역시..

비효율적이지만 간단한 정렬 방법들은 입력 데이터가 많지 않을 때는 사용하기에 부담이 적다. 하지만 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있다면 이 방법들은 적절하지 못하다. 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 분할 정복(divide and conquer)방법에 바탕을 둔다. 분할 정복 방법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분리된 문제가 아직도 해결하기 어렵다면(충분히 작지 않다면) 분할 정복 방법을 연속하여 다시 적용한다. 분할 정복 방법은 대개 순환 호출을 이용하여..

Donald L. Shell 이라는 사람이 제안한 방법이다. 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 아주 빠르다는 것에 착안하여 고안한 방법이다. 셸 정렬은 삽입정렬의 보다 빠르다. 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동하는 것이다. 만약, 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야한다. 셸 정렬은 요소들이 멀리 떨어진 위치로도 이동이 가능하다. 삽입 정렬은 전체의 리스트를 한 번에 정렬하는데 비해, 셸 정렬은 그렇지않다. 1. 정렬할 리스트를 일정기준에 따라 분류하여 연속적이지 않은 여러 개의 부분리스트를 만든다. 2. 모든 부분 리스트를 삽입 정렬을 이용하여 정렬 3. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은..

버블 정렬은 오름차순 기준으로, 인접한 2개의 레코드를 비교하여 정렬되어 있지 않다면 서로 교환하는 비교-교환 과정을 처음부터 끝까지 비교한다. 한 회전에서 2개의 레코드를 계속 비교하기 때문에 각 회전마다 그 리스트의 가장 큰 숫자는 항상 제자리(맨 뒤쪽)로 찾아간다. 1. 리스트의 첫 번째, 두 번째 숫자를 선택 2. 이 둘을 비교, 순서가 맞지 않으면 서로 교환 3. 1회전이 끝나면 가장 큰 숫자는 뒤로 가게 된다. 4. 위 과정을 정렬이 안된 리스트에서 반복 예를 들어 요소의 갯수가 5개이고 3 2 6 1 5 라는 배열이 있다면 1회전 - 2 3 6 1 5 2회전 - 2 3 6 1 5 3회전 - 2 3 1 6 5 4회전 - 2 3 1 5 6 위와 같은 절차가 1번의 스캔이다. 다른 정렬은 1번의 ..

삽입 정렬은 오름차순 기준으로, 정렬이 완료된 기존의 카드 사이에 올바른 자리를 찾아 삽입하는 정렬이다. 1. 정렬되어 있지 않은 리스트의 첫 번째 숫자를 선택 2. 자신을 기준으로 인덱스를 감소시키며(뒤에 부터) 하나 씩 비교해 가며 자신보다 작은 숫자를 찾는다. 3. 자신보다 크다면 그 숫자를 뒤로 한 칸 미룬다. 4. 자신보다 작다면 연산을 멈춘다. 5. 위 과정을 정렬되어 있지 않은 리스트의 마지막 요소까지 반복 주의할 점은, index를 앞에서 부터 비교하는 것이 아니라 뒤에서 부터 비교한다. 즉, (자신의 인덱스-1)번부터 0번까지비교하여 인덱스가 점점 감소한다. 그리고 첫 회전에서 시작은 0번이 아니라 1번부터 시작한다. 예를 들어 요소의 갯수가 5개이고 3 2 6 1 5 라는 배열이 있다면..

선택 정렬은 오름차순 기준으로 1회전 시 마다, 가장 작은 숫자를 선택하여 맨 앞으로 차례대로 정렬하는 기법이다. 입력 배열 외에는 다른 추가 메모리를 요구하지 않는, 즉 한 리스트안에서 교환해여 해결하는 것을 제자리 정렬(in-place sorting)이라고 한다. 1. 입력 배열에서 정렬되지 않은 값 중 최솟값을 검색 2. 이 최솟값을 배열의 1 번째 요소와 교환 3. 1 번째 요소(배열 중 최솟값, 정렬이 완료된 요소)를 제외한 나머지 값 중에서 가장 작은 값을 검색 4. 이 최솟값을 배열의 두 번째 요소와 교환 5. 이 과정을 배열요소갯수-1만큼 되풀이 주의할 점은, index값이 0에서 n-2까지만 변화된다. 만약 A[0]부터 A[n-2]까지 정렬되어 있다면 이미 A[n-1]이 가장 큰 값이기 ..