수행 시간2 알고리즘 7장 - 정렬 문제 : 퀵 정렬 - 알고리즘 7장- 정렬 문제 : 퀵 정렬 - 퀵 정렬은 크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러 개의 문제로 바꾸어서 푸는 방법을 사용한다. 이런 방법을 divide-and-conquer paradigm라고 한다. 이를 수행하기 위해 Partitioning을 사용하여 정렬을 한다. Pivot element를 사용하여 Pivot element 왼쪽에는 Pivot 보다 작은 수들을 오른쪽에는 Pivot 보다 큰 값을 가지도록 정렬을 한다. Pivot을 계속 설정하여 위의 과정을 반복하여 수행하면 배열이 오름차순으로 정렬이 되게 된다. 퀵 정렬의 경우 Pivot을 어떻게 잡아서 Partitioning을 수행하는지가 매우 중요한 요건이라고 할 수 있다. 예를 들어 생각을 해보자. 라는.. 2017. 6. 7. 알고리즘 6장 - 정렬 문제 : 힙 정렬(2) - 알고리즘 6장- 정렬 문제 : 힙 정렬(2) - 앞 장에서 힙 정렬에 대한 개념을 알아보았다면 이번 장에서는 힙 구조를 만드는 것에 대해 중점을 두고 힙 정렬에 대해 살펴볼 것이다. 따라서 개념에 대한 부분을 보고자 하면 알고리즘 5장을 보면 될 것이다. Max 힙 구조를 만드는 코드를 한 번 살펴보자. Max 힙 구조는 부모 노드의 값이 자식 노드의 값보다 큰 이진 트리 구조를 나타낸다. Max 힙을 만드는 방법은 위에서 밑으로 만드는 것이 아니라 밑에서 위로 만든다고 할 수 있다. 만약 위에서부터 만들게 되면 밑으로 내려갈 때 마다 Max 힙의 구조를 만족시키는지를 확인해야하지만 밑에서 만들면 밑에서 트리 구조를 만족하는지만 생각하면 되기 때문에 수행 시간에서 단축될 수 있다. 여기서 length의 .. 2017. 6. 7. 이전 1 다음
