[자료구조/알고리즘] - 퀵정렬, 힙정렬, 위상 정렬

01. 퀵정렬 (quick sort)

퀵 정렬은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘이다. 분할 정복 알고리즘의 하나이다.

• 퀵 정렬은 한 요소인 피벗(pivot)을 지정하여 기준점으로 잡는다.
• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 분할 정복 알고리즘의 한 종류로, 평균적으로 매우 빠른 속도를 가진다.
• 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

퀵정렬은 다음과 같은 순서로 이루어진다.

1. 리스트 중에서 하나의 원소를 고른다. 이 원소를 피벗(pivot) 으로 지정한다.
2. 피벗 앞으로는 피벗보다 값이 작은 원소들이 오고, 뒤로는 피벗보다 값이 큰 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다.
   1. 리스트가 둘로 나뉘는 것을 분할 이라한다.
   2. 분할을 마친 뒤, 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 리스트에 대해 재귀적으로 위 과정을 반복한다. (리스트의 크기가 1 이하일 떄 까지)

퀵정렬 - 예시

1. 피벗은 p, 리스트 왼쪽 끝과 오른쪽 끝에서 시작한 인덱스들을 l, r

5 - 3 - 7 - 6 - 2 - 1 - 4 
                        p

2. 리스트 왼쪽에 있는 l 위치의 값이 피벗 값보다 크고, 오른쪽에 있는 r 위치의 값은 피벗 값보다 작으므로 둘을 교환한다.

5 - 3 - 7 - 6 - 2 - 1 - 4 
l                   r   p 

1 - 3 - 7 - 6 - 2 - 5 - 4 
l                   r   p 

3. r 위치의 값이 피벗 값보다 작지만, l 위치의 값도 피벗값보다 작으므로 교환하지 않는다.

1 - 3 - 7 - 6 - 2 - 5 - 4 
    l           r       p 

4. l 위치를 피벗 값보다 큰 값이 나올 때까지 진행해 r 위치의 값과 교환한다.

1 - 3 - 7 - 6 - 2 - 5 - 4 
        l       r       p 
1 - 3 - 2 - 6 - 7 - 5 - 4 
        l       r       p 

5. l 위치가 r 위치보다 커지면, l 위치의 값과 피벗 값을 교환한다.

1 - 3 - 2 - 6 - 7 - 5 - 4 
                        p 
1 - 3 - 2 - 4 - 7 - 5 - 6 
            p             

6. 피벗 값 좌우의 리스트에 대해 각각 퀵 정렬을 재귀적으로 수행한다.

1 - 3 - 2       7 - 5 - 6
1 - 2 - 3       5 - 6 - 7

7. 완성된 리스트는 다음과 같다.

1 - 2 - 3 - 4 - 5 - 6 - 7

퀵정렬 특징

• 장점
  • 속도가 빠르다.(퀵!)
    • 시간 복잡도 O(nlogn)을 가진 다른 정렬알고리즘과 비교했을 때도 가장 빠름.
  • 추가 메모리 공간이 필요하지 않음.
    • O(logn)만큼의 메모리를 필요로 한다.
• 단점
  • 정렬된 리스트에 대해서는 퀵정렬 분할로 인해 수행시간이 더 소요된다.
  • 퀵정렬 불균형 분할을 방지하기 위해 피벗을 선택할 때 신중해야한다.
    • 단점을 해결하기 위해서 임의의 요소를 선택 후 중간 값을 선택하는 식으로 피벗을 선택.
• 시간복잡도
  • 최선의 경우 n만큼 파티션을 나누는데 그때 마다 데이터가 절반씩 줄어들어서 O(nlogn)
  • 최악의 경우 O(n2) 을 가지게 된다.
    • 순환 호출의 깊이가 n
    • 특히 이미 정렬된 리스트에 대하여 퀵정렬을 시도하는 경우.
    • 순환 호출 깊이 * 각 순환 호출 단계 비교연산 = n2
  • 평균적으로 O(nlogn) 이다.
    • 시간복잡도 O(nlogn)인 다른 정렬알고리즘과 비교했을 떄도 가장 빠르다.
    • 불필요한 데이터 이동을 줄이고, 한번 결정된 피벗은 추후 연산에 사용되지 않기 떄문.

---

02. 힙정렬 (heap sort)

최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 알고리즘

힙은 완전이진트리의 일종이며 최솟값, 최대값을 쉽게 추출할 수 있는 구조이다.

배열로 최대 힙을 구성한 뒤 정렬하는 순서이다.

1. n개의 노드에 대한 완전이진트리를 구성한다. 루트를 기준으로 부모, 왼쪽자식, 오른쪽자식 순서로 구성
2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말한다.
3. 아랫부분의 작은 부분트리부터 시작해 올라가는 방식(bottom-up)으로 전체 배열을 최대 힙으로 만든다.
4. 힙에서 가장 큰 값인 루트를 배열의 가장 마지막 값과 바꾼다. (마지막에 가장 큰 수인 루트가 정렬)
5. 다시 힙의 구조가 유지되도록 정리한다.
6. 4~5번 작업을 모든 숫자가 완료 상태가 될 때까지 반복

힙정렬 - 예시

출처 : https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

힙정렬 특징

• 장점
  • 시간복잡도가 좋은편
  • 힙정렬이 유용한 경우는 전체 자료 정렬보다 가장 큰 값 몇 개만 필요한 경우
    
• 시간복잡도
  • 이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성하는 과정이 트리의 깊이만큼 -> O(logn)
  • 요소의 개수 n개 이므로 O(nlogn) 의 시간복잡도를 가진다.

---

03. 위상정렬 (topological sort)

순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘

• 사이클이 없는 방향 그래프(DAG) 의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열을 한다.
• 위상정렬은 DFS를 이용해서 구현할 수 있으며, 큐를 이용해서 구현할 수도 있다.

큐를 이용한 위상정렬의 순서는 다음과 같다.

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣기
3. 각 노드가 큐에 들어온 순서가 위상정렬 수행 결과

위상정렬 - 예시

출처 : https://guides.codepath.com/compsci/Topological-Sort#implementation

관련 예시

1. 각각의 작업이 완료되어야만 끝나는 프로젝트
2. 선수 과목

위상정렬 특징

• 위상 정렬은 DAG에 대해서만 수행

  • DAG(Direct Acyclic Graph): 순환하지 않는 방향 그래프

• 위상 정렬에는 여러가지 답이 존재할 수 있음

  • 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답이 존재

• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단

  • 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못함

• 스택을 활용한 DFS를 이용해 위상 정렬 수행할 수 있음

• 시간복잡도

  • 위상 정렬을 위해 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거해야한다.
    • 위상 정렬 알고리즘 시간복잡도 O(V + E)

---

References

• 퀵정렬-위키백과
• 힙정렬-위키백과
• https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-algorithm.html
• https://www.youtube.com/watch?v=xeSz3pROPS8