트리 정렬이란 이진 탐색 트리를 이용하여 정렬하는 방법이다. 정렬할 원소들을 이진 탐색 트리로 구성하고, 중위 우선 순회 방법을 사용한다. 중위 순회의 경로가 오름차순 정렬이 된다. 트리 정렬 수행 과정 정렬되지 않은 {30, 3, 49, 12, 1, 24, 5} 를 트리 정렬을 통해 과정을 살펴보자. 1. 정렬되지 않은 자료를 이진 탐색 트리로 구성한다. 2. 중위 순회 연산을 시행하면 순회 순서가 정렬 값이다. 중위 순회 순서: 1, 3, 5, 12, 24, 30, 49 트리 정렬 복잡도 분석 메모리 공간 사용 원소 n개의 대하여 n개의 메모리 사용 크기 n의 이진 탐색 트리 저장 공간 연산 시간 n개의 노드에 대한 시간 복잡도 O(nlog2 n)
히프정렬이란? 히프는 우선 순위 큐를 완전 이진 트리로 구현하는 방법으로 히프는 최대 값이나 최소 값을 쉽게 추출할 수 있는 자료구조이다. 최소 히프의 부모 노드 값은 자식 노드의 값 보다 작다. 이런 최소 히프의 특성을 이용하여 정렬을 하는 것이다. 히프정렬 수행 방법 최소히프를 이용하는 방법과 최대히프를 이용하는 방법 총 2가지가 있다. 최대히프를 이용한 수행 방법 정렬할 원소들을 입력하여 최대 히프로 구성한다. 최상단 노드를 배열의 마지막 자리에 배치하고 삭제한다. 나머지 원소에 대해 다시 최대 히프로 재구성한다. 원소의 개수 만큼 위 과정을 반복 수행한다. 히프정렬 수행 과정 {25, 1, 24, 20, 7, 2, 8, 18} 의 자료를 히프 정렬을 수행해보자. 1. 정렬할 8개의 원소를 완전 이..
퀵정렬이란 찰스 앤터니 리처드 호어가 개발한 정렬 방법으로, 평균적으로 매우 빠른 정렬 방법이다. 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 분할 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다. 합병 정렬과 달리 리스트를 비균등하게 분할한다. 퀵정렬 수행 순서 리스트 안에 있는 한 원소를 피벗으로 선택한다. 피벗보다 작은 원소는 피벗의 왼쪽에, 피벗보다 큰 원소는 피벗의 오른쪽에 배치한다. 피벗을 제외하고 피벗의 왼쪽과 오른쪽을 2개의 부분집합으로 보고 이 두 부분집합에 대해서 위 방법을 반복한다. 피벗을 왼쪽 끝으로 할 경우의 퀵정렬 왼쪽 끝에서 움직이면서 크기를 비교하여 피벗보다 큰 원소를 찾아 low로 표시한다. 오른쪽 끝에서 왼쪽으로 움직이면서 피벗보다 ..
선택 정렬 정렬하기 전 데이터에서 가장 작은 값을 추출해 자리를 교환하고 그 다음 값을 추출해 자리를 교환하는 방식으로 정렬 수행 방법 전체 원소 중에서 가장 작은 원소를 찾아 첫번째 원소와 자리를 교환한다 그 다음 두 번째로 작은 원소를 찾아 두 번째 원소와 자리를 교환한다 반복.. 왼쪽과 오른쪽에 두 개의 리스트가 있다고 가정해보자. 왼쪽 리스트에는 정렬한 값을 넣을 것이고 오른쪽 리스트는 정렬하기 전의 값이 있다. 가장 작은 원소를 찾아 왼쪽 리스트에 넣고 그 다음 작은 값을 찾아 왼쪽 리스트에 또 넣는다. 오른쪽 리스트가 공백이 될 때까지 반복한다. 만약 위와 같은 방식으로 배열로 구현한다고 하면, 똑같은 크기의 배열이 2개나 필요하다. 메모리 공간 절약을 위해 하나의 배열을 사용하며 가장 작은 ..
