[알고리즘] 정렬 (개선 ver)

 

 

앞서 소개한 정렬에 대해 공부하며 개선된 방식을 소개해볼까 한다.

 

병합 정렬 (개선 ver)

첫째로, 이전 글에서 작성한 병합 정렬 코드의 성능 최적화를 위해 다음과 같은 방법을 사용했다. 

1. 임시 배열 사용: 병합 과정에서 사용할 임시 배열을 미리 할당하여 메모리 할당을 최소화
2. 배열 복사 최소화: 병합 과정에서 정렬된 배열을 원본 배열로 복사하는 작업을 최소화
3. 인플레이스 병합: 병합 과정에서 인덱스를 사용하여 배열 요소를 직접 교환하여 성능을 개선

아래는 코드 예시이다.

function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}

// 병합 과정에서 사용할 임시 배열을 미리 할당
let tempArray = new Array(arr.length);

function sort(arr, tempArray, leftStart, rightEnd) {
if (leftStart >= rightEnd) {
return;
}
let mid = Math.floor((leftStart + rightEnd) / 2);
sort(arr, tempArray, leftStart, mid);
sort(arr, tempArray, mid + 1, rightEnd);
merge(arr, tempArray, leftStart, rightEnd);
}

function merge(arr, tempArray, leftStart, rightEnd) {
let leftEnd = Math.floor((leftStart + rightEnd) / 2);
let rightStart = leftEnd + 1;
let left = leftStart;
let right = rightStart;
let index = leftStart;

while (left <= leftEnd && right <= rightEnd) {
if (arr[left] <= arr[right]) {
tempArray[index] = arr[left];
left += 1;
} else {
tempArray[index] = arr[right];
right += 1;
}
index += 1;
}

// 남은 요소들 처리
while (left <= leftEnd) {
tempArray[index] = arr[left];
left += 1;
index += 1;
}
while (right <= rightEnd) {
tempArray[index] = arr[right];
right += 1;
index += 1;
}

// 정렬된 부분을 원본 배열에 복사
for (let i = leftStart; i <= rightEnd; i++) {
arr[i] = tempArray[i];
}
}

sort(arr, tempArray, 0, arr.length - 1);
return arr;
}

// 사용 예시
let array = [5, 2, 9, 1, 5, 6];
console.log(mergeSort(array));

 

 

퀵 정렬 (개선 ver)

앞서 작성한 퀵 정렬을 개선하기 위해서는 현대의 팀소트 방식을 도입할 수 있다는 것을 배웠다.

예를 들어, 배열의 크기가 작을 경우 삽입정렬을 채택하는 것이다. 왜냐하면 삽입정렬의 경우 배열크기가 적을 수록 효율적이기 때문이다.

여기서 팀소트란 파이썬 개발자가 만튼 파이썬의 기본 정렬 알고리즘이지만 우수한 성능으로 자바스크립트를 비롯한 다양한 언어에 적극적으로 채택되었다고 한다. 예를 들어, 자바에서는 윈시 자료형처럼 안정성이 중요하지 않을 경우에만 제한적으로 퀵 정렬을 사용하고 있다고 한다. 

function quickSort(arr) {
quick_sort(arr, 0, arr.length - 1);
return arr;
}

function quick_sort(arr, left, right) {
// 배열이 작을 경우 삽입 정렬 사용
if (right - left < 10) {
insertionSort(arr, left, right);
return;
}

if (left < right) {
let pivot = medianOfThree(arr, left, right);
let partitionIndex = partition(arr, left, right, pivot);
quick_sort(arr, left, partitionIndex - 1);
quick_sort(arr, partitionIndex + 1, right);
}
}

function partition(arr, left, right, pivot) {
let start = left;
let end = right;

while (start <= end) {
while (arr[start] < pivot) start++;
while (arr[end] > pivot) end--;
if (start <= end) {
// 버블 정렬과 동일한 개선
[arr[start], arr[end]] = [arr[end], arr[start]];
start++;
end--;
}
}
return start;
}

//  중앙값을 피벗으로 사용, 랜덤으로도 사용가능
function medianOfThree(arr, left, right) {
let mid = Math.floor((left + right) / 2);
if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
if (arr[mid] > arr[right]) [arr[mid], arr[right]] = [arr[right], arr[mid]];
return arr[mid];
}

function insertionSort(arr, left, right) {
for (let i = left + 1; i <= right; i++) {
let current = arr[i];
let j = i - 1;
while (j >= left && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}

// 사용 예시
let array = [5, 2, 9, 1, 5, 6];
console.log(quickSort(array));