병합 정렬은 분할 정복 기법을 기반으로 한 정렬 기법입니다. 최악의 경우 시간 복잡도는 Ο(n log n)입니다. 그러나 이 알고리즘은 추가 O(n) 메모리를 사용하므로 공간 측면에서 추가 비용이 발생합니다.
이제 이 알고리즘을 구현하는 방법을 살펴보겠습니다. mergeSort 및 merge라는 2개의 함수를 생성하겠습니다.
병합 - 이 함수는 2개의 인수를 취하며, 이는 2개의 부분 배열이며 올바른 순서로 요소를 삽입하여 하나로 연결합니다.
병합 정렬 - 이 함수는 배열의 왼쪽과 오른쪽 절반에서 mergeSort를 재귀적으로 호출한 다음 merge를 사용하여 이러한 배열 부분을 함께 결합합니다. 구현을 보면 훨씬 더 명확해질 것입니다.
병합 기능으로 시작하여 바로 코드에 뛰어들 수 있습니다. −
예시
function merge(left, right) {
let mergedArr = [];
let i = 0;
let j = 0;
// Try merging till we reach end of either one of the arrays.
while (i < left.length && j < right.length) {
if (compare(left[i], right[j])) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
// If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
// the for loop above would stop once it reaches the end of
// The left array leaving 3 elements in the right array
// In order to add the remaining elements from either array,
// We need to add elements from i to end in left and j to end
// in the right array to the merged array.
return mergedArr.concat(left.slice(i)).concat(right.slice(j));
} 이 함수는 2개의 정렬된 배열을 가져와 더 큰 배열로 정렬된 상태를 유지하도록 O(n) 시간에 병합합니다. 방법에 대한 자세한 설명은 코드 주석을 참조하십시오. -
를 사용하여 이를 테스트할 수 있습니다.예시
let a1 = [1, 2, 3, 5] let a2 = [4, 6, 8, 9] console.log(merge(a1, a2))
출력
[1, 2, 3, 4, 5, 8, 9]
이제 mergesort 함수에서 이 함수를 사용하여 실제로 전체 배열을 정렬합니다.
우리는 mergeSort를 위한 내부 함수를 생성할 것이고, 우리의 함수가 확장 가능하도록 비교기를 사용할 수 있도록 외부 함수로 래핑할 것입니다. 이 내부 함수를 살펴보겠습니다 -
예시
function mergeSortInner(arr) {
if (arr.length < 2) {
return arr;
}
let mid = Math.floor(arr.length / 2);
// Create an array from 0 to mid - 1 elements
let left = arr.slice(0, mid);
// Create an array from mid to the last element
let right = arr.slice(mid);
// Sort the left half, sort the right half,
// merge the sorted arrays and return
return merge(mergeSortInner(left), mergeSortInner(right));
} 이 함수는 배열을 두 개로 나누고 개별적으로 정렬한 다음 병합된 배열을 다시 반환합니다.
테스트를 통해 전체 코드를 살펴보겠습니다 −
예시
function mergeSort(arr, compare = (a, b) => a < b) {
function merge(left, right) {
let mergedArr = [];
let i = 0;
let j = 0;
// Try merging till we reach end of either one of the arrays.
while (i < left.length && j < right.length) {
if (compare(left[i], right[j])) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
// If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
// the for loop above would stop once it reaches the end of
// The left array leaving 3 elements in the right array
// In order to add the remaining elements from either array,
// We need to add elements from i to end in left and j to end
// in the right array to the merged array.
return mergedArr.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSortInner(arr) {
if (arr.length < 2) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSortInner(left), mergeSortInner(right));
}
// Call inner mergesort to sort and return the array for us.
return mergeSortInner(arr);
}
You can test this using:
let arr = [5, 8, 9, 12, -8, 31, 2];
// Sort Array elements in increasing order
arr = mergeSort(arr);
console.log(arr);
// Sort Array elements in decreasing order
arr = mergeSort(arr, (a, b) => a > b);
console.log(arr);
arr = [
{
name: "Harry",
age: 20
},
{
name: "Jacob",
age: 25
},
{
name: "Mary",
age: 12
}
];
// Sort Array elements in increasing order alphabetically by names
arr = mergeSort(arr, (a, b) => a.name < b.name);
console.log(arr);
// Sort Array elements in decreasing order of ages
arr = mergeSort(arr, (a, b) => a.age < b.age);
console.log(arr); 출력
[ -8, 2, 5, 8, 9, 12, 31 ]
[ 31, 12, 9, 8, 5, 2, -8 ]
[
{ name: 'Harry', age: 20 },
{ name: 'Jacob', age: 25 },
{ name: 'Mary', age: 12 }
]
[
{ name: 'Mary', age: 12 },
{ name: 'Harry', age: 20 },
{ name: 'Jacob', age: 25 }
] 빠른 정렬
빠른 정렬은 매우 효율적인 정렬 알고리즘이며 데이터 배열을 더 작은 배열로 분할하는 것을 기반으로 합니다. 큰 배열은 두 개의 배열로 분할되며, 그 중 하나는 지정된 값(예:피벗)보다 작은 값을 보유하며, 이를 기반으로 파티션이 만들어지고 다른 배열은 피벗 값보다 큰 값을 보유합니다.
빠른 정렬은 배열을 분할한 다음 자신을 재귀적으로 두 번 호출하여 두 개의 결과 하위 배열을 정렬합니다. 이 알고리즘은 평균 및 최악의 경우 복잡도가 Ο(n2)(n은 항목 수)이므로 대규모 데이터 세트에 매우 효율적입니다.
파티션 프로세스
다음 애니메이션 표현은 배열에서 피벗 값을 찾는 방법을 설명합니다.https://www.tutorialspoint.com/data_structures_algorithms/images/quick_sort_partition_animation.gif
피벗 값은 목록을 두 부분으로 나눕니다. 그리고 재귀적으로 모든 목록에 하나의 요소만 포함될 때까지 각 하위 목록에 대한 피벗을 찾습니다.
파티셔닝에서 우리가 하는 일은 배열에서 첫 번째 요소(무작위 빠른 정렬의 임의 요소)를 선택한 다음 나머지 배열을 이 요소와 비교하는 것입니다. 그런 다음 이 요소보다 작은 모든 요소를 피벗 인덱스의 왼쪽으로 이동하고 이보다 큰 값을 피벗 인덱스의 오른쪽으로 이동합니다. 따라서 끝에 도달하면 피벗 요소(첫 번째 요소)가 올바른 위치에 배치됩니다.
그보다 큰 모든 요소는 오른쪽에 있고 그보다 작은 요소는 왼쪽에 있으므로 이 요소가 올바른 위치에 있게 하기 때문입니다. 이 분할 프로세스를 확장하여 왼쪽 및 오른쪽 하위 배열에서 파티션을 재귀적으로 호출하여 정렬을 돕습니다.
다음과 같이 파티션 기능을 구현할 수 있습니다 -
예시
function partition(arr, low, high, compare) {
let pivotIndex = low + 1;
for (let i = pivotIndex; i < high; i++) {
if (compare(arr[i], arr[low])) {
// Swap the number less than the pivot
swap(arr, i, pivotIndex);
pivotIndex += 1;
}
}
// Place the pivot to its correct position
swap(arr, pivotIndex - 1, low);
// Return pivot's position
return pivotIndex - 1;
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
You can test the partition function using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
console.log(partition(arr, 0, arr.length, (l, r) => l < r));
console.log(arr); 출력
4 [ -6, 1, 3, 2, 5, 10, 8, 45, 9 ]
5의 왼쪽에 있는 요소는 5보다 작고 오른쪽에 있는 요소는 5보다 큽니다. 또한 5의 인덱스가 4임을 알 수 있습니다.
이제 빠른 정렬이 작동하는 방식을 살펴보겠습니다 -
1 요소보다 큰 창이 있는 경우 배열의 파티션을 낮은 값에서 높은 값으로 호출하고 반환된 인덱스를 사용하여 배열의 왼쪽 및 오른쪽 절반에 대한 퀵소트를 호출합니다.
예시
function QuickSort(arr, low, high, compare = (l, r) => l < r) {
if (high - low > 0) {
// Partition the array
let mid = partition(arr, low, high, compare);
// Recursively sort the left half
QuickSort(arr, low, mid, compare);
// Recursively sort the right half
QuickSort(arr, mid + 1, high, compare);
}
}
You can test this using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
QuickSort(arr, 0, arr.length, (l, r) => l < r);
console.log(arr); 출력
[ -6, 1, 2, 3, 5, 8, 9, 10, 45 ]