트리 정렬(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.
버블 정렬(Bubble Sort)
버블 정렬(Bubble Sort) '인접'한 두개의 원소를 비교하여 자리를 교환하는 방식으로 정렬. 처음부터 마지막 원소까지 반복하면서 가장 큰 원소가 마지막으로 정렬된다. 평균 비교 횟수와 평균 자리 교환 횟수는 n(n-1)/2 이다. 따라서 시간 복잡도는 O(n^2)가 된다. 예시) {57, 16, 41, 2, 50, 6} 1. 인접한 두 원소를 비교하여 자리를 교환하는 작업을 마지막 원소까지 반복하여 가장 큰 원소를 마지막 자리로 옮긴다. {57, 16, 41, 2, 50, 6} ===> {16, 57, 41, 2, 50, 6} ===> {16, 41, 57, 2, 50, 6} ===> {16, 41, 2, 57, 50, 6} ===> {16, 41, 2, 50, 57, 6} ===> {..
2021. 4. 2.
선택 정렬(Selection Sort)
선택 정렬(Selection Sort) 기준 위치에 맞는 원소를 '선택'하여 자리를 교환하는 방식으로 정렬. 전체 비교 횟수는 n개의 원소에 대해 n(n-1)/2 이고, 어떤 경우에서나 비교 횟수가 같기 때문에 시간 복잡도는 O(n^2)이다. 예시) {57, 16, 41, 2, 50, 6} 1. 첫 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다. {57, 16, 41, 2, 50, 6} 기준 위치 가장 작은 원소 2 ====> {2, 16, 41, 57, 50, 6} 2. 두 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다. {2, 16, 41, 57, 50, 6} 기준 위치 가장 작은 원소 6 ====> {2, 6, 41, 57, 5..
2021. 4. 2.
