JS sort_algolithm7 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. merge Sort ( 합병정렬 ) 합병정렬이란? 위의 그림과 같은 방식으로 작동해 배열을 정렬시켜주는 알고리즘입니다. 합병 정렬은 비교 기반 정렬 알고리즘으로 시간복잡도는 O(NlogN)입니다. 시간복잡도 최악 시간복잡도: O(nlogn) 평균 시간복잡도: O(nlogn) 최선 시간복잡도: O(nlogn) 합병정렬 javascript로 구현하기 병합정렬은 크게 두 가지 함수로 이루어져 있다. function merge(left, right) : 이미 소팅된 배열 left, right 받아서 하나로 합치는 순수한 함수 function mergeSort(arr) : 배열을 반으로 쪼개서 merge 함수에게 left, right 인자를 넘겨주는 함수 이 때, merge함수는 순수한 함수이고, mergeSort는 재귀로 함수를 콜한다는 것을 인.. 2021. 12. 15. Selection Sort(선택 정렬) Selection Sort 선택 정렬은 매우 단순한 정렬 알고리즘으로 구현하기 매우 쉬운 알고리즘이다. 선택 정렬 알고리즘은 이렇게 진행된다. 먼저 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교환한다. 이제 맨 앞을 제외하고 다시 순회하며 최소값을 찾는다. 그 값을 맨 앞 위치 바로 다음 위치와 교체한다. ... 반복 버블 정렬이 각 회전이 끝날 때마다 맨 마지막 데이터의 위치가 정해졌던 것과 반대로 선택 정렬은 n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해진다. 다음의 그림을 보면 이해가 쉽다. 장점 선택 정렬도 위의 두 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있으며 알고리즘이 직관적이므로 이해하기도 쉽고 구현하기도 쉽다. 단.. 2021. 12. 9. Insertion Sort(삽입 정렬) Insertion Sort 삽입 정렬은 왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여 알맞은 자리에 삽입하는 형식의 정렬 방법이다. 삽입 정렬은 위 그림처럼 항상 두 번째 요소를 왼쪽 요소와 비교하면서 시작한다. 1회전에서는 왼쪽 요소보다 두번째 요소가 크기 때문에 아무런 일이 일어나지 않는다. 2회전에서는 2를 왼쪽 두 개의 데이터와 비교하여 가장 왼쪽에 끼워넣는다. 3회전에서는 5를 왼쪽 데이터와 비교하여 3과 7 사이에 끼워넣는다. 이런식으로 회전을 하다보면 정렬이 되는 방식이다. 삽입 정렬은 항상 왼쪽 비교 대상 데이터들이 정렬되어있다는 가정하에 진행된다. 장점 삽입 정렬도 버블 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있다. 또한 구현하기 매우 .. 2021. 12. 9. Bubble Sort(버블 정렬) Bubble Sort 버블 정렬은 요소들이 마치 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고 해서 버블 정렬이란 이름이 붙여졌다. 버블 정렬은 말로 설명하는 것보다 눈으로 보는 것이 이해하기 쉽기 때문에 아래 gif 이미지를 첨부하였다. 위 그림을 보면 알 수 있듯이 데이터를 두개씩 묶어서 비교한 후 크기가 큰 쪽이 오른쪽으로 가도록 자리를 바꿔가며 크기가 큰 데이터를 오른쪽으로 민다. 그러면 1회전이 끝남과 동시에 이 리스트에서 가장 큰 값이 가장 오른쪽에 가기 때문에 맨 오른쪽 자리가 결정난다. 즉, n번째 정렬 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정된다. 장점 버블 정렬은 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있다. 여기서 "in place"라는 것은 자료.. 2021. 12. 9. 이전 1 2 다음
