절취선 블로그

정렬 알고리즘 중 가장 빠른 성능을 가짐 시간 복잡도 : 평균 : O( n log(n) ) 최악의 경우 : O(n^2) 피벗 : 배열의 정 중앙위치의 값 분할 정복 방법을 아용하여 배열을 정렬하는 방법으로 피벗을 중심으로 배열을 둘로 나누어 값을 비교하여 정렬 1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가..

힙: 부모의 값이 자식의 값보다 항상크다. 힙을 사용하여 정령하는 알고리즘으로 완전이진트리 형대의 알고리즘 시간 복잡도 : n log(n) n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다. 2와 3을 반복한다.