배열을 더 작은 배열로 나누는 방식. 0개 또는 1개로 구성된 배열이 될 때까지 나눈 다음 다시 합치면서 정렬을 한다.
합병 정렬은 재귀를 쓴다. slice를 재귀로 사용해 0,1개의 요소가 남을 때까지 작게 쪼갠다. 이후 합병 함수를 사용해 다시 합친다.
시간 복잡도는 O(nlogn), 공간 복잡도는 O(n)
function merge(arr1, arr2){ //두 개의 배열을 정렬할 때, 합병 정렬의 한 부분
let results = [];
let i = 0;
let j = 0;
while(i < arr1.length && j < arr2.length){ //하나의 배열이 다 순환할 때까지
if(arr2[j] > arr1[i]){
results.push(arr1[i]);
i++;
} else {
results.push(arr2[j])
j++;
}
}
while(i < arr1.length) { //하나의 배열이 다 순환되고 남은 배열을 순환시키도록 함.
results.push(arr1[i])
i++;
}
while(j < arr2.length) {
results.push(arr2[j])
j++;
}
return results;
}
function mergeSort(arr){ //slice로 반으로 쪼개 배열의 요소가 1개 혹은 0개가 될 때까지 재귀로 돌림
if(arr.length <= 1) return arr;
let mid = Math.floor(arr.length/2); //반으로 나눠줌
let left = mergeSort(arr.slice(0,mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
// 1개가 남을 때까지 재귀가 실행되고, 1개가 남으면 리턴해서 그 위의 함수(부모 함수)에 인수로 들어가게 됨
// left = num1 1개 남은 left 인수, right = num2 1개 남은 right 인수
// merge(left, right)가 되어 쭉 합병을 하며 거슬러 올라감
1개 혹은 0개로 남은 배열을 위 merge 함수로 합쳐줌
위 과정에서 4개의 요소 중 2번 쪼갰기 때문에 logn이 되고, 합치는 게 n번 되므로 nlogn이 된다.
2. 퀵 정렬
첫 번째 요소를 기준(피벗)으로 한 바퀴 순회 하면서 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬해 준다.
순회를 마치고 첫 번째 요소보다 큰 값 중 첫 번째 값의 바로 앞에 위치시키면서 해당 위치에 있던 요소와 자리를 바꾼다. 바꿨으면 그 요소는 순회를 거치지 않고 고정시켜 준다.
첫 번째 요소의 위치가 바뀌고 위 과정을 반복해 준다.
퀵 정렬도 재귀로 실행한다.
시간 복잡도는 O(nlogn)~O(n^2)이지만, 피벗을 첫 번째 요소가 아닌 중간 값으로 한다면 O(nlogn)으로 바꿀 수 있다.
function pivot(arr, start=0, end=arr.length+1){ // [4,2,1,3,5,7,8,6]
function swap(array, i, j) { //배열에서 자리 바꿔주는 함수
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var pivot = arr[start]; // 초기 피벗
var swapIdx = start; // 초기 피벗 인덱스
for(var i = start + 1; i < arr.length; i++){
if(pivot > arr[i]){ // 피벗 보다 작은 값이면 피벗 인덱스를 1올리고 작은 값과 피벗 인덱스의 위치를 바꿈
swapIdx++;
swap(arr,swapIdx,i);
}
}
swap(arr,start,swapIdx); // 마지막으로 첫 번째 요소와 피벗 인덱스의 값과 자리를 바꿔주고
return swapIdx; // 피벗 인덱스를 리턴함 => 3
}
// 피벗(기준 인덱스)을 바꾸는 과정. 처음 피벗은 첫 번째 인덱스
function quickSort(arr, left = 0, right = arr.length -1){
if(left < right){ //조건을 달지 않으면 무한대로 실행하기 때문에 비교할게 있을때만 실행되도록 한다.
let pivotIndex = pivot(arr, left, right) //3
//left
quickSort(arr,left,pivotIndex-1);
//right
quickSort(arr,pivotIndex+1,right);
}
return arr;
}
3. 기수(정수) 정렬
여태까지 본 정렬은 다른 요소와 비교하면서 정렬을 했었는데, 기수 정렬은 비교를 하지 않고 정렬한다.
숫자(정수)로 된 배열만 가능하다.
시간 복잡도는 O(nk), 공간 복잡도는 O(n+k) => k는 자릿수로 자릿수가 높은 요소가 있으면 시간복잡도가 굉장히 늘어난다.
0~9까지 된 공간 안에 일의 자리 기준으로 정렬을 해준다. 그리고 이렇게 정렬한 것을 다시 배열로 바꿔준다.
이제 자릿수를 올리면서 반복한다. 만약 자릿수를 올렸는데 해당 자릿수가 없는 숫자의 경우 0에 집어넣는다.
function getDigit(num, i) { //원하는 자리수의 값 구하기
return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
function digitCount(num) { //자리수 구하기
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1; //밑이 10인 로그임
}
function mostDigits(nums) { //최대자리수 구하기
let maxDigits = 0;
for (let i = 0; i < nums.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(nums[i]));
}
return maxDigits;
}
function radixSort(nums){
let maxDigitCount = mostDigits(nums); // 배열 중 최대 자리 수 구하기
for(let k = 0; k < maxDigitCount; k++){ //1,10,100,...최대자리수 순회
let digitBuckets = Array.from({length: 10}, () => []); //0~9를 넣을 빈 배열 10개 생성
for(let i = 0; i < nums.length; i++){ //배열 순회
let digit = getDigit(nums[i],k); //해당 자리 수 값 구하기
digitBuckets[digit].push(nums[i]); //해당 자리 수 값(0~9)를 위에 만든 빈 배열에 쌓기
}
nums = [].concat(...digitBuckets); //한 번 순회하고 배열 합친 다음 k++하여 실행됨
}
return nums;
}
