JS sort_algolithm/UnStable Sort3 Heap Sort ( 힙 정렬 ) 힙(Heap) 힙이란? 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 heap 은 우선순위 큐를 위해서 만들어진 트리자료구조이다. 힙에는 최소힙과 최대힙이 있음 heap의 특징 heap은 완전이진트리의 형태이다. 완전이진트리 설명보러가기 heap은 트리내에서 중복된 값을 허용한다. heap은 느슨한 정렬(반 정렬) 상태를 가진다. 최소힙 작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 함 최대힙 가장 큰 값이 맨 위에 오도록 함. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있음 힙 정렬을 다시 말하자면, 최소 힙이나 최대 힙을 이용하여 정렬하는 방법입니다. 내림차순 정렬을 위해서는 최대 힙을 사용하고, 오름차순 .. 2021. 12. 16. Quick Sort ( 퀵 정렬 ) Quick Sort 퀵 정렬은 1960년에 찰스 앤터니 리처드 호어(C.A.R hoare)가 처음 제안한 방법으로 이후 많은 사람들이 수정 보완하여 완성된 정렬 알고리즘이다. 이 알고리즘은 처음 소개된 이후로 반세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중에 하나이다. 퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다. in place가 아닌 방법이 더 직관적으로 이해하기 쉬우므로 이 방법을 먼저 정리하고 그 다음 in place 방법을 정리하겠다. Basic Quick Sort - Not In Place 퀵 정렬은 분할정복 전략을 사용한 알고리즘이다. 즉, 정렬하는데 가장 간단한 배열은 바로 요.. 2021. 12. 16. Selection Sort(선택 정렬) Selection Sort 선택 정렬은 매우 단순한 정렬 알고리즘으로 구현하기 매우 쉬운 알고리즘이다. 선택 정렬 알고리즘은 이렇게 진행된다. 먼저 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교환한다. 이제 맨 앞을 제외하고 다시 순회하며 최소값을 찾는다. 그 값을 맨 앞 위치 바로 다음 위치와 교체한다. ... 반복 버블 정렬이 각 회전이 끝날 때마다 맨 마지막 데이터의 위치가 정해졌던 것과 반대로 선택 정렬은 n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해진다. 다음의 그림을 보면 이해가 쉽다. 장점 선택 정렬도 위의 두 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있으며 알고리즘이 직관적이므로 이해하기도 쉽고 구현하기도 쉽다. 단.. 2021. 12. 9. 이전 1 다음
