정렬 알고리즘 -2 (퀵/힙/합병)

퀵정렬

  • 기본개념

    분할정복 알고리즘의 하나로 이름에서 알수있듯이 평균적으로 매우 빠른 수행 속도를 자랑한다. 리스트중 하나의 요소를 선택하여 선택요소보다 작은 값을 좌측, 큰값을 우측으로 나누어 정렬해나가며 더이상 분할이 불가능 할때까지 반복한다.

  • 정렬 진행순서 [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]

완료