퀵정렬, 힙정렬, 2-way 합병정렬(merge sort)

#정보처리기사 #개발자의도구들 #퀵정렬 #힙정렬 #2way합병정렬 #mergesort

​

24년도 1회차 정보처리기사 필기 시험대비 공부를 진행하였습니다.

\* 본글은 PC버전에 최적화 되어있습니다.

​

**\\ **공부방법론은 가장 첫글에 있습니다. 참고하실 분들은 참고하세요! \\ - 개발자의도구들

\\ 정보처리기사 전체 총 정리는 여기 있습니다!! \\

2과목 소프트웨어 개발

sort\_algoritm

​

퀵 정렬(Qucik Sort)

​

키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일로 분할 시키는 방식입니다.

​

분할정복법의 일종입니다.

​

평균 수행 시간복잡도는 O(nlogn)이고, 최악의 경우 O(N²)까지 걸릴 수 있습니다.

​

---

힙 정렬(heap Sort)

힙 정렬은 전이진 트리(Complete Binary Tree)를 이용한 정렬 방식입니다.

​

구성된 전이진 트리를 Heap Tree로 변한하여 정렬합니다.

​

평균과 최악 모두 O(nlogn)의 시간복잡도를 가집니다.

​

---

2-Way 합병정렬(Mege Sort)

이미 정렬되어있는 두 개의 파일을 한개의 파일로 합병하는 정렬 방식입니다.

​

평균과 최악 모두 O(nlogn)의 시간복잡도를 가집니다.

​

평균과 최악 모두 O(nlogn)의 시간복잡도를 가집

​

​