퀵정렬
- 기본개념
분할정복 알고리즘의 하나로 이름에서 알수있듯이 평균적으로 매우 빠른 수행 속도를 자랑한다. 리스트중 하나의 요소를 선택하여 선택요소보다 작은 값을 좌측, 큰값을 우측으로 나누어 정렬해나가며 더이상 분할이 불가능 할때까지 반복한다.
- 정렬 진행순서
[8,5,4,3,9,2,7,6,1]
1회 : index(1)을 Pivot으로 잡고 left , right 를 가운데로 축소시키며 left는 pivot 값보다 큰값을 찾고 right는 pivot 값보다 작은 값을 찾아 자리바꾸기를 통한 좌우 정렬 진행후 pivot값을 가운데로 이동시키며 두개의 리스트로 분할
<리스트내 swap>
[[8],5,4,3,9,2,7,6,1]
^ ^
pivot left right
<Pivot값 swap>
[[8],5,4,3,1,2,7,6,9]
^ ^
<분할>
[6,5,4,3,1,2,7][8][9]
2회: 분할된 리스트를 1회에서 진행한것같이 반복.
[[6],5,4,3,1,2,7][8][9]
^ ^
[[6],5,4,3,1,2,7][8][9]
^ ^
[2,5,4,3,1][6][7][8][9]
3회: 반복
[[2],5,4,3,1][6][7][8][9]
^ ^
[[2],1,4,3,5][6][7][8][9]
^ ^
[1][2][4,3,5][6][7][8][9]
4회: 반복
[1][2][[4],3,5][6][7][8][9]
^ ^
[1][2][3][4][5][6][7][8][9]
완료
힙정렬
- 기본개념
완전 이진트리의 일종으로 최소값, 최대값을 쉽게 추출할수 있는 자료구조인 ‘힙’을 이용한 정렬로써, 최대힙 트리나 최소 힘 트리를 구성해 정렬을 하는 방법이다. 힙트리를 구성해 데이터를 삽입하면 정렬데이터 상태로 삽입됨으로써 그자체로 정렬이 이루어진다.
- 자세한 내용은 [힙] (https://taes-k.github.io/docs/algorithm/algorithm-heap/)
합병정렬
- 기본개념
퀵소트와 마찬가지로 분할정복 알고리즘으로써, 분할이 불가능 할때까지 분할후, 합치면서 작은단위로써 정렬을 실행한다.
- 정렬 진행순서
[8,5,4,3,9,2,7,6,1]
1회 : 분할.
[8,5,4,3,9,2,7,6,1]
[8][5][4][3][9][2][7][6][1]
2회 : 합병
[8][5] [4][3] [9][2] [7][6] [1]
[5,8] [3,4] [2,9] [6,7] [1]
3회 : 합병
[5,8][3,4] [2,9][6,7] [1]
[3,4,5,8] [2,6,7,9] [1]
3회 : 합병
[3,4,5,8] [2,6,7,9] [1]
[2,3,4,5,6,7,8,9] [1]
4회 : 합병
[2,3,4,5,6,7,8,9] [1]
[1,2,3,4,5,6,7,8,9]
완료