JS sort_algolithm/Stable Sort3 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. 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 다음
