합병정렬(병합정렬, Merge Sort) - 전체 데이터를 하나의 단위로 분할한 후 분할한 것들을 다시 병합하는 정렬 방식 - 분할 정복 알고리즘에 속함 (분할 정복 : 어떤 문제를 그대로 해결할 수 없을 때 작은 문제로 분할해서 푸는 방법) 시간 복잡도 O(NlogN) - 최선이든 최악이든 같음 장점 - 어떠한 경우에도 좋은 성능을 보장한다. - 중복된 데이터의 순서가 바뀌지 않는 stable한 정렬이다. 단점 - 30 개 이하의 숫자를 정렬할 때는 삽입 정렬과 별 차이가 없음 - 정렬하는데 추가 메모리가 필요함 (in-place 알고리즘이 아님) 구현 function mergeSort(array) { if (array.length < 2) { return array; } let pivot = Math..

문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbers return [6, 10, ..

빠른 정렬(퀵 정렬, Quick Sort) 빠른 정렬(퀵 정렬)은 기준점을 획득한 다음 해당 기준점을 기준으로 배열은 나눈다. (한 쪽에는 기준점보다 작은 항목들이 위치하고 다른 쪽에는 기준점보다 큰 항목들이 위치한다.) 이런 식으로 모든 항목이 정렬될 때까지 이 과정을 반복한다. 우선 기준점을 나타내는 변수를 pivot이라고 지정하고, 기준점을 기준으로 왼쪽에는 기준점보다 작은 항목들이 위치하도록 하고 오른쪽에는 기준점보다 큰 항목들이 위치하도록 한다. 나뉘어진 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하여, 모든 배열이 기본 배열(요소가 하나뿐인 배열)이 될 때까지 반복하면 된다. 이 때 기준점을 정하는 기준은 없으며 보통의 경우에는 배열의 첫번째 원소 / 배열의 마지막 원소 / 물리적으로 중앙에 ..

버블 정렬(거품 정렬, Bubble Sort) 버블 정렬이란? 버블 정렬은 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 시간 복잡도 O(n^2) 공간 복잡도 O(1) 장점 in-place 알고리즘이기 때문에 메모리가 절약된다. 구현하기가 쉽다. 단점 다른 정렬 알고리즘은 배열의 이미 정렬된 부분을 활용하는데 비해 거품 정렬은 모든 가능한 짝을 비교하기 때문에 성능이 안좋은 정렬 중에서도 가장 안좋은 편에 속한다. function bubbleSort(array) { let temp; for (let i = 0; i < array.length - 1; i++) { for (let j = 0; j..

삽입 정렬 삽입 정렬이란? 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다. 동작 과정 예를 들어 [3, 7, 2, 5, 1, 4]의 배열을 오름차순으로 정리한다고 하면 첫번째 숫자는 놔두고 두번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣는다. 세번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣는다. 이렇게 끝까지 계속 한다. 시간 복잡도 Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우 Best Case: O(n): 이미 정렬이 되어있는 경우 공간 복잡도 O(1) 장점 메모리가 절약된다. (배열을 새로 만들 필요 없이 주어진 배열 안에서 정렬시키면 되기 때문, in pla..

정렬 중에 그나마 빠른 힙정렬의 경우에도 시간복잡도 O(Nlog₂N)인데 계수정렬은 시간복잡도가 O(N)으로 굉장히 빠르다. 💥그러나 정렬해야할 수의 범위가 작을 때에만 유리하다는 것을 유의해야 한다 -> 정렬해야할 수가 0,100,2,10,1000 이라면 고작 5개의 수를 정렬하는데 0부터 1000까지 배열을 만들어야 하기 때문에 메모리가 낭비되고 반복문도 불필요하게 돌아야 한다. 방법은 간단하다. 정렬해야 할 수가 [5,2,3,1,4,2,3,5,1,7] 이라면 1. 주어진 원소들을 반복문으로 돌며 각 원소의 개수를 카운팅한다. 2. 카운팅한 개수만큼 원소들을 나열해준다. 이 때 각 원소의 개수를 카운팅 하기 위해서 원소 중에 가장 큰 수 + 1의 배열 array를 만들어서 모두 0으로 채워주고 (+1..