이번 포스팅에서는 데이터를 다루면서 정말로 많이 사용하게 되는 정렬 알고리즘에 대해서 다루도록 하겠습니다.
정렬 알고리즘의 종류는 정말 다양합니다. 각각의 알고리즘 마다 장점과 단점이 존재하므로 데이터의 형태에 따라서 가장 효율적인 알고리즘을 적용하는 것이 좋습니다. 그렇기 때문에 많은 정렬 알고리즘을 알고 있는 것이 유리합니다.
기본적인 정렬 알고리즘인 버블, 선택, 삽입 정렬부터 합병, 지수, 퀵 정렬까지 알아보겠습니다. 기본적으로 숫자를 요소로 가지는 배열을 오름차순으로 정렬하는 것으로 가정하겠습니다.
비교식 정렬
비교식 정렬은 정렬하려는 요소의 개수가 적은 경우에 적합합니다.
버블 정렬(Bubble Sort)
버블 정렬을 배열의 요소 2개를 비교하여 가장 큰 요소를 배열의 마지막 인덱스로 이동 시키는 것 입니다. 한번 루프를 돌 때마다 가장 큰 요소가 마지막에 인덱스 위치에 배치됩니다. 이 경우 for문이 중첩 되기 때문에 시간복잡도는 O(n²), N 제곱시간입니다.
function bubbleSort(arr) {
for(let i = 0; i < arr.length; i++) {
for(let j=1; j < arr.length; j++) {
if(arr[j] > arr[j+1]) {
let temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}버블 정렬 최적화
숫자 하나가 정렬될 때마다 정렬된 숫자를 제외시키고 루프 반복
i의 초기값을 배열의 길이로 지정하고 루프가 한번 돌때마다 i값을 1씩 감소시킵니다. 그리고 j값이 i값보다 작을 때까지만 각 요소의 크기를 비교합니다.
function bubbleSort(arr) {
for(let i = arr.length; i > 0; i--) {
for(let j=1; j < i-1; j++) {
if(arr[j] > arr[j+1]) {
let temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}정렬이 완료된 경우 루프 종료 시키기
Swaps이라는 변수를 선언하고 반복이 시작될 때 false값을 할당합니다. 그리고 배열의 각 요소를 비교해서 요소의 위치가 변경될 경우 Swrap을 true로 변경시킵니다. 그리고 새로운 반복이 시작 될 때 Swarps를 false로 초기화 합니다. 배열을 한번 순회 한 후에 Swrap값이 변하지 않는다는 것은 정렬이 완료되었다는 것을 의미하기 때문에 반복문을 종료시킵니다.
function bubbleSort(arr) {
let Swaps;
for(let i = arr.length; i > 0; i--) {
Swarps = false; // 반복이 시작 될 때 false값 할당
for(let j=1; j < i-1; j++) {
if(arr[j] > arr[j+1]) {
let temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
Swrap = true;
}
}
if(!Swrap) = break; // 더 이상 정렬이 필요 없을 경우 반복문을 종료
}
return arr;
}버블 정렬 정리
버블 정렬의 시간복잡도를 고려하면 효율적인 알고리즘이 아닐 수 있습니다. 하지만 거의 정렬이 완료된 배열이고 정렬시켜야하는 요소가 적은 경우에는 최적화를 통해서 선형시간에 가까운 효율을 낼 수 있습니다.
선택 정렬(Selection Sort)
배열을 순회하며 최솟값을 찾아 마지막에 맨앞에 있는 요소와 최소값을 가지는 요소의 위치를 바꿉니다. 두 번째 반복에서는 두 번째 요소부터 나머지 요소들의 순회하고 최소값가지는 요소와 두번째 요소의 위치를 바꿉니다. 이런 동작을 반복하며 배열을 정렬합니다. 선택 정렬의 시간복잡도는 O(n²), N 제곱시간입니다.
function selectionSort(arr) {
for(let i = 0; i < arr.length; i++) {
let min = i;
let temp = '';
for(j = i+1; j < arr.length; j++) {
if(arr[min] > arr[j]){
min = j
}
}
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
return arr;
}삽입 정렬(Insertion Sort)
한 번에 하나의 요소를 올바른 위치에 삽입해서 배열의 정렬된 부분을 늘려나갑니다. 두 번째 요소를 첫 번째 요소와 비교해서 정렬합니다. 그리고 세 번째 요소의 위치를 정해야하는데 이 때 선택지는 세가지입니다. 첫 번째 요소 앞으로 삽입하거나 첫 번째 요소와 두 번째 요소 사이로 삽입하거나 제자리에 위치하는 것 입니다. 이런 방식으로 배열을 순회하면서 각 요소를 적합한 위치에 삽입합니다.
function insertionSort(arr) {
for(let i=1; i < arr.length; i++) { // 배열의 두번째 요소 부터 순회합니다.
let current = arr[i] // 비교할 요소를 current 변수에 할당합니다.
for(let j=i-1; j >= 0; j--) { // current 변수의 앞에 있는 요소부터 왼쪽 방향으로 순회 합니다.
if(current < arr[j]) { // 크기를 비교해서 왼쪽에 있는 요소가 클 경우 두 값을 바꿉니다.
arr[j+1] = arr[j];
arr[j] = current;
}
}
}
return arr
}다른 구현 방식
const insertionSort = function (arr) {
let sorted = [arr[0]];
for (let i = 1; i < arr.length; i++) {
if (arr[i] >= sorted[i - 1]) {
sorted.push(arr[i]);
} else {
for (let j = 0; j < i; j++) {
if (arr[i] <= sorted[j]) {
const left = sorted.slice(0, j);
const right = sorted.slice(j);
sorted = left.concat(arr[i], right);
break;
}
}
}
}
return sorted;
};병합 정렬(Merge sort)
버블 정렬, 선택 정렬, 삽입 정렬과 같은 기본적인 정렬은 데이터가 많은 경우에 사용하기에 불리합니다. 특정 조건외에는 O(n²)의 시간복잡도를 가지기 때문입니다.
병합 정렬은 배열이 분할 될 때, O(logn)의 시간복잡도를 가지고 분할한 요소들을 비교할때 O(n)의 시간복잡도를 가집니다. 그래서 최종적으로 시간복잡도를 O(nlogn)를 가지기 때문에 데이터가 많은 경우에 매우 유리합니다.
데이터가 정렬된 정도와 상관없이 정렬할 경우 최선의 방법이라 할 수 있습니다.
병합 정렬 알고리즘에는 분할, 병합, 정렬의 개념이 모두 사용됩니다. 재귀를 통해 배열의 요소가 1개 또는 0개가 될 때까지 분해하고 다시 합쳐 나가면서 정렬을 이어 나갑니다.
병합 함수 및 정렬 구현
정렬된 두 배열을 병합하면서 새로운 정렬된 배열을 만드는 함수를 구현합니다.
function merge(arr1, arr2) {
const result = [];
let i = 0; // arr1 인덱스
let j = 0; // arr2 인덱스
// 포인터를 이용하여 각 요소를 비교해서 새로운 배열에 추가합니다.
while (i < arr1.length && j < arr2.length) {
if(arr1[i] < arr2[j]) {
result.push(arr1[i]);
i++
} else {
result.push(arr2[j]);
j++
}
}
// 배열의 길이가 다를 경우 남은 배열의 요소를 추가합니다.
while (i < arr1.length) {
result.push(arr1[i]);
i++;
}
while (j < arr2.length) {
result.push(arr2[j]);
j++;
}
return result;
}
function mergeSort(arr) {
// arr : [10, 24, 76, 73]
if(arr.length <=1) return arr;
// 배열 길이가 1개 또는 0개가 될 때 까지 절반으로 자른 후 왼쪽 부터 merge 함수를 이용해서 합치기
let mid = Math.floor(arr.length/2) // 가운데 인덱스
let left = mergeSort(arr.slice(0, mid)); // 왼쪽 배열 1. left : [10] 4. left : [76]
let right = mergeSort(arr.slice(mid)); // 오른쪽 배열 2. right : [24] 5. right : [73]
return merge(left, right); // 3. merge([10], [24]) => [10, 24] 6. merge([76], [73]) => [73, 76]
// 마지막으로 merge([10, 24], [73, 76]) 실행 => [10, 24, 73, 76]
}퀵 정렬(Quick Sort)
퀵 정렬은 병합 정렬과 같이 재귀를 통해 데이터를 분할하여 정렬합니다. 다만 피벗 포인트라는 단일 요소를 선택하여 수행한다는 점에서 차이가 있습니다. 피벗 포인트와 비교하여 작은 숫자는 왼쪽으로 큰 숫자는 오른쪽으로 옮깁니다.
이동이 끝나는 순간 피벗 포인트의 인덱스가 정해집니다. 그리고 다른 요소를 새로운 피벗 포인트로 지정하고 같은 작업을 반복합니다. 작업이 반복될 때마다 피벗 포인트로 지정된 요소들의 인덱스가 정해집니다.
퀵 정렬은 최대 O(nlogn)의 시간 복잡도를 가집니다. 하지만 O(n²)의 시간 복잡도를 가질 수 있습니다. 예를들어 정렬이 되어 있는 n개의 요소를 가진 배열에 첫번째 요소를 피벗으로 지정하여 배열을 분해할 경우, 이 작업은 O(n)의 시간복잡도를 가지며, 분해된 배열요소를 각각 비교해야하므로 이 또한 O(n)의 시간복잡도를 가집니다.
즉, 분해, 비교에 각각 O(n)의 시간복잡도를 가지므로 최종적으로 O(n²)의 시간 복잡도를 가지게 되는 것 입니다. 퀵 정렬은 매우 효율적이지만 정렬이 되어 있을 경우는 최악의 성능을 보여줄 수 있기 때문에 주의해야합니다.
피벗 함수 및 정렬 구현
우선 피벗 포인트를 지정하고 비벗을 기준으로 정렬하는 함수를 선언합니다. 이 함수는 피벗을 기준으로 데이터를 나누고 정렬된 피벗의 인덱스를 반환합니다.
function pivot(arr, start=0, end=arr.length-1) {
let pivot = arr[start];
let swapIdx = start; // swap할 인덱스를 추적
// 배열의 요소를 바꾸는 함수
function swap(array, i, j) {
let temp = array[i];
array[i] = array[j]
array[j] = temp;
}
for(let i= start+1; i < arr.length; i++) {
if(pivot > arr[i]){
swapIdx++; // pivot 보다 작은 요소를 만날 때 마다 1씩 증가
swap(arr, swapIdx, i);
}
}
swap(arr, swapIdx, start);
return swapIdx;
}
function quickSort(arr, left = 0, right = arr.length-1) {
if(left < right) {
let pivotIdx = pivot(arr, left, right);
// 왼쪽 정렬
quickSort(arr, left, pivotIdx-1);
// 오른쪽 정렬
quickSort(arr, pivotIdx+1, right);
}
return arr;
}다른 구현 방식
재귀를 이용해서 왼쪽 배열과 오른쪽 배열에 요소를 추가하여 합치는 방법도 있습니다.
const quickSort = function (arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] <= pivot) left.push(arr[i]);
else right.push(arr[i]);
}
const lSorted = quickSort(left);
const rSorted = quickSort(right);
return [...lSorted, pivot, ...rSorted];
};비교하지 않는 정렬
기수 정렬
기수정렬은 값들의 비교가 아닌 숫자의 특성을 이용해서 정렬하는 방법입니다. 각 요소가 정수인 요소를 가지는 배열에서 각 요소의 자릿수를 이용하여 정렬합니다. 우선 0~9까지 버킷을 만들고 각 요소의 자리수를 해당하는 버킷에 넣습니다.
- 정수의 자리 수에 맞는 버킷에 요소들을 버킷에 넣습니다.
2.숫자가 작은 버킷에서 부터 차례대로 숫자를 꺼내오면 1의자리 수 기준으로 정렬된 배열을 얻을 수 있습니다.
이 후, 10의 자리, 100의 자리로 반복하면 최종적으로 정렬이 완성된 배열을 얻을 수 있습니다.
기수정렬을 구현하기 위해서는 2가지 정보가 필요합니다.
- 숫자의 몇번째 자리에 무슨 숫자가 있는지 => 예를들어, 902의 1의 자리 => 2
- 숫자중 가장 큰 자릿수 => 가장 큰 자릿수 만큼 버킷에 넣고 꺼내는 작업을 반복해야 합니다.
우선, 두 가지 정보를 얻을 수 있는 함수 3개를 구현합니다. digitCount 함수는 mostDigits에서 각 숫자의 자릿수를 계산하기 위한 함수입니다.
// 숫자의 몇번째 자리에 무슨 숫자가 있는지 리턴
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;
}
// 배열의 숫자 중 가장 큰 자릿수 리턴
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 maxDigits = mostDigits(nums);
for(let i=0; i< maxDigits; i++) {
// 빈 배열 10개를 가지는 이차원 배열 생성
let digitBuckets = Array.from({length : 10}, () => []);
for(let j=0; j < nums.length; j++) {
let digit = getDigit(nums[j], i);
digitBuckets[digit].push(nums[j]);
}
nums = [].concat(...digitBuckets); // 전개 문법으로 버킷을 합쳐서 다시 nums에 할당
}
return nums;
}
}위의 코드를 보면 반복문이 중첩되어 있으나 maxDigts는 배열의 길이와 상관없은 상수이므로 이 알고리즘의 시간복잡도는 평균적으로 O(KN) 시간복잡도를 가집니다. 이론적으로는 비교정렬에 비해 효율이 좋은 알고리즘입니다. 하지만 컴퓨터가 숫자, 정보를 저장하는 방식에 의해 K가 아닌 logN의 시간이 걸린다는 주장도 있습니다.
