풀풀풀

힙 정렬 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법으로, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 1. 정렬해야할 n개의 요소들로 최대힙(완전 이진 트리 형태)를 만든다. 내림차순 기준 정렬2. 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.3. 삭제되는 요소들(최댓값부터 삭제)는 값이 감소되는 순서로 정렬되게 된다. - 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬방식이다.- 힙은 1차원 배열로 쉽게 구현될 수 있다.- 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값이나 작은 값을 구할 때, 최대 k만큼 떨어진 요소들을 정렬할 때 이다. 시간 복잡도최선/최악/평균 모두 O(n..

퀵 정렬 퀵소트는 divide and conquer 방법을 통해 정렬한다. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피봇이라고 한다.피봇 앞에는 피봇보다 값이 작은 모든 원소들이 오고, 피봇 뒤에는 피봇보다 값이 큰 모든 원소들이 오도록 피봇을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피봇은 더 이상 움직이지 않는다.분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.[ 위키백과 참조 ] 시간 복잡도 ( T(n) 은 n의 리스트를 정렬하는데 걸리는 시간 ) 평균적으로 O(nlog n) 의 시간복잡도를 갖는다. 최선의 경우 : O(nlog n) 최악의 경우 ..