(129 관리 1-13) 트리 정렬(Tree Sort)

 

---

트리 정렬(Tree Sort)

---

멘토링
나무위키에 설명되어 있는 정렬 알고리즘들은 시간 내서 꼭 한 번씩 정독해 보시길 권해 드립니다.

---

트리 정렬

 

이진 탐색 트리를 만들어 정렬하는 방식

 

핵심 키워드

 

이진 탐색 트리, 트리 중위 순회

 

Tree Sort | GeeksforGeeks - YouTube

 

 [4, 6, 1, 7, 5, 8, 2, 3]

 

○ 정렬될 배열의 맨 첫 값이 루트 노드가 된다.

 

○ 다음 값부터는 기존 노드 값과 비교한다. 루트 노드에서 출발해서 추가될 노드 값이 기존 노드 값보다 작은 경우는 왼쪽 자식을, 기존 노드 값보다 크거나 같을 경우는 오른쪽 자식을 찾는다. 내림차순은 반대로 기존 노드 값보다 크면 왼쪽, 작거나 같으면 오른쪽을 찾으면 된다.

 

○ 위 2에서 해당 방향의 자식 노드가 없으면 그 방향의 자식 노드로 추가한다. 있으면 그 방향의 자식 노드로 가서 크기를 비교하고 위 2와 같은 방법으로 해당 방향의 자식 노드가 있으면 계속 그 방향으로 가서 조사하고 없으면 그 방향의 자식 노드로 추가한다.

 

○ 모든 값이 노드로 추가되었으면 해당 트리를 중위 순회 방식으로 순회하여 그 순서대로 값을 정렬해 나간다.

 

 

기출문제

 

(관리 125-4-4)
방향성 비순환 그래프(Directed Acyclic Graph)에 대하여 다음 물음에 답하시오.

가. 방향성 비순환 그래프의 개념과 특징
나. 아래 방향성 비순환 그래프에 대하여 위상정렬(Topology Sort)을 실시하고 결과값 제시

 

(응용 122-4-2)
정렬 알고리즘은 컴퓨터 분야에서 가장 많이 연구된 분야 중 하나이다.

가. 선택정렬(Selection Sort)과 삽입정렬(Insertion Sort), 퀵정렬(Quick Sort) 알고리즘을 설명하시오.
나. 다음 키 값을 갖는 파일을 퀵정렬(Quick Sort) 알고리즘을 사용하여 오름차순으로 정렬하려고 한다.
피벗이 50일 때 수행되는 분할과정을 단계적으로 설명하시오.
(단, n=8 : 50, 80, 20, 90, 40, 10, 30, 60)

 

(관리 99-4-2)
퀵 정렬(Quick sort)알고리즘을 설명하고, 다음 데이터를 퀵 정렬 알고리즘을 사용해서 정렬하는 과정을 설명하시오.

30,15,16,24,38,33,17,29,32

 

(관리 95-2-6)
다음은 C언어로 작성된 버블정렬(Bubble Sort) 알고리즘 프로그램의 일부이다.
프로그램을 완성하시오.

#include

int main() {
 int data[5] = {2, 5, 1, 4, 3};
 bubble(data, 5);
 for(int i=0; i<5; i++) {
   print("%d ", data[i]);
 }
return 0;
}

 

(관리 90-2-4)
정렬(Sorting) 알고리즘의 하나인 삽입정렬(insertion sorting) 알고리즘을 기술하고 이 알고리즘이 어떤 경우에 효과적인지 설명하시오.
또한 평균 연산시간(Big O)과 최악의 연산시간을 근거와 함께 설명하시오.

 

참고 자료

 

정렬 알고리즘 - 나무위키 (namu.wiki)

정렬 알고리즘 - 나무위키