트리 정렬(Tree Sort)
트리 정렬(Tree Sort) 정렬되지 않은 원소들을 이진 탐색 트리(왼쪽 자식 노드에는 자신보다 작은, 오른쪽 자식 노드에는 자신보다 큰 값인 이진 트리)로 구성한 후 중위 순회 방법(현재 노드의 왼쪽 서브 트리로 이동 -> 현재 노드 -> 현재 노드의 오른쪽 서브 트리로 이동)으로 순회하면서 오름차순으로 정렬한다. 시간 복잡도는 O(nlog2n)이다. 예시) {57, 16, 41, 2, 50, 6, 32, 27} 1. 이진 탐색 트리로 구성 57 / 27 /\ 6 41 /\. /\ 2 16 32 50 2. 중위 순회 방법으로 오름차순 정렬 {2, 6, 16, 27, 32, 41, 50, 57} 프로그램 작성) package test; class TreeNode { int data; Tr..
2021. 4. 2.
셸 정렬(Shell Sort)
셸 정렬(Shell Sort) 일정한 간격인 원소들끼리 부분집합으로 묶어 삽입 정렬을 수행하는 작업을 반복하면서 정렬. 삽입 정렬보다 비교, 교환 연산을 줄일 수 있다. 일정한 간격은 매개 변수로 받으며 일반적으로 전체 원소 수의 1/2로 설정하고, 단계를 반복할 때마다 절반으로 감소시키면서 반복한다. 매개변수의 영향으로 인해 성능 분석이 쉽지 않지만 일반적으로 시간 복잡도를 O(n^1.25)로 측정한다. 예시) {57, 16, 41, 2, 50, 6, 32, 27} 1. 일정한 간격을 원소 수의 절반인 4로 설정하고 그에 해당하는 부분집합끼리 삽입 정렬을 수행한다. {57, 16, 41, 2, 50, 6, 32, 27} ===> 57과 50을 삽입 정렬 {50, 16, 41, 2, 57, 6..
2021. 4. 2.
