본문 바로가기
728x90

Algorithm6

병합 정렬(Merge Sort) 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현 분할 정복이란? 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식 빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다. 퀵소트와는 반대로 안정 정렬에 속함 시간복잡도 평균최선최악 Θ(nlogn) Ω(nlogn) O(nlogn) 요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵정렬과 유사 mergeSort function mergeSort(array, left, right) { if (left < right) { const mid = Math.floor((left + right) / 2); mergeSort(array, left, mid); mergeSort(array, mid + 1, right); me.. 2023. 5. 15.
퀵 정렬(Quick Sort) Quick Sort은 '분할 정복(divide and conquer) 방법' 을 통해 주어진 배열을 정렬한다. [분할 정복(divide and conquer) 방법] 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. Quick Sort은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할한다. JavaScript Code function quickSort(arr) { if(arr.length < 2) { return arr } let pivot = [arr[0]] let left = [] let right = [] for(let i = 1;.. 2023. 5. 12.
계수 정렬(Counting Sort) / Comparison Sort N개 원소의 배열이 있을 때, 이를 모두 정렬하는 가짓수는 N! 이다 따라서, Comparison Sort를 통해 생기는 트리의 말단 노드가 N! 이상의 노드 갯수를 갖기 위해서는, 2^h >= N! 를 만족하는 h를 가져야 하고, 이 식을 h > O(nlgn)을 가져야 한다. (h는 트리의 높이,,, 즉 Comparison sort의 시간 복잡도이다) 이런 O(nlgn)을 줄일 수 있는 방법은 Comparison을 하지 않는 것 / Counting Sort 과정 시간 복잡도 : O(n + k) -> k는 배열에서 등장하는 최대값 공간 복잡도 : O(k) -> k만큼의 배열을 만들어야 한다. Counting이 필요 : 각 숫자가 몇 번 등장했는지 센다. JavaScript.. 2023. 5. 11.
삽입 정렬(Insertion Sort) Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다. Insertion Sort는 '2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입' 하여 정렬하는 알고리즘이다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다. 손 안의 카드를 정렬하는 방법과 유사하다. Process 정렬은 2번째 위치(index)의 값을 temp에 저장한다. temp와 이전에 있는 원소들과 비교하며 삽입해나간다. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다. JavaScript Code.. 2023. 5. 10.
728x90

티스토리툴바