코딩 인터뷰를 위한 튜토리얼
데이터 정렬의 중요성과 JavaScript 배열 정렬 알고리즘
데이터 목록을 정렬하는 것은 애플리케이션 개발에서 매우 중요한 부분입니다. 이는 정보 표시 및 검색 효율성을 향상시키는 데 필수적입니다. 따라서 훌륭한 소프트웨어 엔지니어라면 배열을 정렬하는 다양한 방법을 숙지하고 있어야 합니다. 이 글에서는 JavaScript에서 배열을 정렬하는 데 사용되는 몇 가지 주요 알고리즘을 살펴보겠습니다.
정렬이란 무엇이며, 왜 중요할까요?
출처: 언스플래시
정렬이란, 주어진 기준에 따라 값을 체계적으로 배열하는 과정입니다. 이 순서는 오름차순이나 내림차순일 수 있으며, JavaScript에서 배열을 정렬하는 것은 데이터의 의미를 명확하게 만들어 줍니다. 예를 들어, 최신 파일부터 정렬된 파일 목록을 보거나, 가격별로 정렬된 제품 목록을 확인할 수 있습니다. 또한, 정렬된 데이터에서만 효율적으로 작동하는 이진 검색과 같은 알고리즘을 사용할 때도 정렬은 필수적입니다.
JavaScript에는 데이터를 쉽게 정렬할 수 있는 내장 함수와 라이브러리가 존재하지만, 코딩 인터뷰나 하위 수준 코드를 작성해야 할 때는 정렬 알고리즘이 내부적으로 어떻게 작동하는지 이해하는 것이 중요합니다.
JavaScript 배열 정렬 알고리즘
버블 정렬
버블 정렬은 이해하고 구현하기 가장 쉬운 알고리즘 중 하나입니다. 이 알고리즘은 배열을 여러 번 반복하면서, 각 반복마다 인접한 두 요소를 비교하여 순서가 잘못된 경우 서로 교환합니다. 배열의 요소 수만큼 반복하며, 각 반복이 끝날 때마다 배열의 끝부분부터 정렬됩니다. 오름차순으로 숫자를 정렬하기 위한 의사 코드는 다음과 같습니다.
| 1. 배열의 요소 수를 n이라고 합니다. |
| 2. i를 사용하여 반복 횟수를 추적하면서 n번 반복합니다.(각 반복에서 다음 작업을 수행합니다.) |
| a. 배열의 두 번째 요소부터 (n-i)번째 요소까지 반복합니다. |
| b. 이전 요소가 현재 요소보다 크면 두 요소를 교환합니다. |
이를 JavaScript 코드로 표현하면 다음과 같습니다.
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
이 알고리즘의 동작 방식을 더 명확하게 이해하기 위해 각 패스에서 배열이 어떻게 변경되는지 console.log를 사용하여 확인하는 것이 좋습니다. 아래 코드는 각 패스마다 배열의 변화를 출력하도록 수정된 버블 정렬 함수와, 이 함수를 사용하여 정렬된 작은 배열의 예시를 보여줍니다.
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
console.log(`Pass: ${i}`);
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
console.log(arr);
}
}
return arr;
}
const array = [9, 2, 7, 4, 1];
sort(array);
console.log(array);
위 코드를 실행한 결과는 다음과 같습니다.
버블 정렬의 시간 복잡도는 O(n^2)으로, 각 패스마다 배열을 반복하는 n번의 패스를 수행하기 때문입니다. 따라서 데이터 크기가 커질수록 효율성이 떨어집니다. 하지만, 추가적인 메모리를 거의 사용하지 않고 배열 요소를 제자리에서 수정하므로 공간 복잡도는 O(1)입니다.
삽입 정렬
삽입 정렬은 또 다른 인기 있는 JavaScript 배열 정렬 알고리즘입니다. 이 알고리즘은 배열의 두 번째 요소부터 시작하여 각 요소를 이미 정렬된 부분에 올바른 위치에 삽입하는 방식으로 작동합니다. 배열의 각 요소를 선택하여 num이라고 하면, num 왼쪽에 있는 모든 숫자가 num보다 작아질 때까지 num을 왼쪽으로 이동시킵니다. 이 과정을 배열의 두 번째 요소부터 마지막 요소까지 반복하면 모든 숫자가 정렬됩니다. 다음은 의사 코드로 표현한 설명입니다.
| 1. 배열의 요소 수를 n이라고 합니다. |
| 2. i를 1부터 n-1까지 반복합니다.(두 번째 요소부터 시작) |
| a. currentElement를 array[i]로 설정합니다. |
| b. j를 i - 1로 설정합니다. |
| c. j가 0보다 크거나 같고 array[j]가 currentElement보다 크면 다음을 반복합니다. |
| i. array[j]를 array[j+1]로 이동합니다. |
| ii. j를 1 감소시킵니다. |
| d. array[j+1]를 currentElement로 설정합니다. |
다음은 위 의사 코드를 JavaScript로 구현한 코드입니다.
function insertionSort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
}
return array;
}
버블 정렬과 마찬가지로, console.log를 추가하여 알고리즘의 작동 방식을 시각화하는 것이 도움이 됩니다. 아래 코드는 삽입 정렬이 어떻게 작동하는지 보여줍니다.
function sort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
console.log("Placing element:", currentElement);
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
console.log("Placed it at position:", j + 1);
console.log(array);
}
return array;
}
const array = [4, 1, 2, 5, 3];
sort(array);
위 코드 조각을 실행하면 다음과 같은 결과가 출력됩니다.
병합 정렬
삽입 정렬과 버블 정렬은 O(n^2)의 시간 복잡도를 가지는 반면, 병합 정렬은 O(n * log(n))의 시간 복잡도를 갖는 준선형 알고리즘입니다. 병합 정렬은 분할 정복 방식을 사용합니다. 먼저 배열을 요소가 하나만 남을 때까지 재귀적으로 더 작은 배열로 나눕니다. 분할된 배열은 이후 다시 병합되는데, 이 때 하위 배열들이 정렬된 상태로 합쳐집니다.
병합 과정은 두 개의 정렬된 배열을 합치는 것과 동일한 방식으로 진행됩니다. 병합 정렬 알고리즘의 의사 코드는 다음과 같습니다.
| 1. 배열의 길이가 1 이하이면 배열을 반환합니다.(기본 케이스) |
| 2. 중간 인덱스를 찾습니다.
a. mid를 (배열 길이 / 2)의 내림 값으로 설정합니다. |
| 3. 배열을 두 개의 하위 배열로 나눕니다.
a. leftArray를 만들고 배열의 첫 번째 절반을 복사합니다.(인덱스 0부터 mid까지) b. rightArray를 만들고 배열의 두 번째 절반을 복사합니다.(인덱스 mid+1부터 끝까지) |
| 4. leftArray에 대해 MergeSort를 재귀적으로 호출합니다. |
| 5. rightArray에 대해 MergeSort를 재귀적으로 호출합니다. |
| 6. 정렬된 두 개의 하위 배열을 병합합니다.
a. 빈 resultArray를 만듭니다. b. leftArray와 rightArray가 모두 비어 있지 않은 동안 다음을 반복합니다. i. leftArray의 첫 번째 요소가 rightArray의 첫 번째 요소보다 작거나 같으면 해당 요소를 resultArray에 추가합니다. ii. 그렇지 않으면 rightArray의 첫 번째 요소를 resultArray에 추가합니다. c. leftArray에 남아 있는 모든 요소를 resultArray에 추가합니다.(있는 경우) d. rightArray에 남아 있는 모든 요소를 resultArray에 추가합니다.(있는 경우) |
| 7. resultArray를 반환합니다. |
이를 JavaScript로 구현한 결과는 다음과 같습니다.
function sort(array) {
// Base case in which we stop subdividing the array
if (array.length == 1) {
return array;
}
// Finding the middle point of the array
const m = Math.round(array.length / 2);
// Divide the array into two halves
const leftUnsorted = array.slice(0, m);
const rightUnsorted = array.slice(m);
// Recursively call merge sort
const leftSorted = sort(leftUnsorted);
const rightSorted = sort(rightUnsorted);
// Return a merged sorted array
return merge(leftSorted, rightSorted);
}
function merge(left, right) {
// Merge two sorted lists
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex += 1;
} else {
result.push(right[rightIndex]);
rightIndex += 1;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
예시 배열을 사용하여 코드를 실행하면 정상적으로 작동하는 것을 확인할 수 있습니다.
퀵 정렬
병합 정렬과 마찬가지로 퀵 정렬도 분할 정복 전략을 사용합니다. 이 알고리즘은 배열에서 피벗 요소를 선택한 다음, 피벗보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 이동시키는 방식으로 작동합니다. 이 과정이 완료되면 피벗은 배열 내에서 올바른 위치에 있게 됩니다.
피벗 주변의 요소를 재배치하기 위해, 퀵 정렬은 우선 피벗을 배열의 끝으로 이동시킵니다. 그 후, 배열의 왼쪽부터 시작하여 피벗보다 큰 첫 번째 숫자를 찾고, 동시에 배열의 오른쪽부터 시작하여 피벗보다 작은 첫 번째 숫자를 찾습니다. 두 숫자를 찾으면 서로 교환합니다. 이 과정을 왼쪽 포인터가 오른쪽 포인터보다 커질 때까지 반복합니다.
이후, 마지막으로 피벗과 교환한 두 숫자 중 큰 숫자를 피벗과 교환합니다. 이 시점에서 피벗은 올바른 위치에 있게 되며, 피벗보다 작은 숫자는 왼쪽, 큰 숫자는 오른쪽에 위치합니다. 이 과정은 하위 배열에 요소가 하나만 남을 때까지 피벗의 왼쪽과 오른쪽 하위 배열에 대해 재귀적으로 반복됩니다.
퀵 정렬의 의사 코드는 다음과 같습니다.
| 1. lessThanPointer가 greaterThanPointer보다 작으면 다음을 수행합니다.
a. 배열에서 피벗 요소를 선택합니다. b. 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 이동하도록 요소를 재배치합니다. c. 왼쪽 하위 배열에 대해 Quicksort를 재귀적으로 호출합니다. d. 오른쪽 하위 배열에 대해 Quicksort를 재귀적으로 호출합니다. |
다음은 위 의사 코드를 JavaScript로 구현한 것입니다.
function sort(array, low, high) {
if (low < high) {
// Choose the pivot index and partition the array
const pivotIndex = move(array, low, high);
// Recursively sort the subarrays to the left and right of the pivot
sort(array, low, pivotIndex - 1);
sort(array, pivotIndex + 1, high);
}
}
function move(array, low, high) {
// Select the pivot element (in this case, the last element)
const pivotElement = array[high];
// Initialize the index for the smaller element
let i = low - 1;
for (let j = low; j < high; j++) {
// If the current element is less than or equal to the pivot, swap it with the element at index i+1
if (array[j] <= pivotElement) {
i += 1;
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Swap the pivot element into its correct position
const temp = array[i];
array[i] = array[j];
array[j] = temp;
// Return the index of the pivot element
return i + 1;
}
Node.js 환경에서 퀵 정렬을 사용하여 예시 배열을 정렬하면 다음과 같은 결과를 얻을 수 있습니다.
최선의 경우 퀵 정렬은 준선형 시간 복잡도로 실행됩니다. 또한, 퀵 정렬의 공간 사용량은 로그 함수에 비례하여 증가하므로 다른 JavaScript 배열 정렬 알고리즘에 비해 비교적 효율적입니다.
코딩 인터뷰를 위한 팁
❇️ 연습은 필수입니다. 다양한 알고리즘을 학습하는 것도 중요하지만, 문제 해결 능력과 컴퓨팅 사고력을 키우는 것이 더욱 중요합니다. 리트코드 및 알고 엑스퍼트와 같은 플랫폼을 이용하여 꾸준히 연습하는 것이 좋습니다.
❇️ 문제에 바로 접근하기보다 먼저 스스로 해결하려고 노력하십시오. 이 과정을 통해 문제 해결 능력을 향상시킬 수 있습니다.
❇️ 만약 문제를 너무 오래 붙잡고 있다면, 해결 방법을 참조하십시오. 솔루션 분석을 통해 문제 해결 방법을 배울 수 있습니다. 많은 학습 플랫폼에서 솔루션을 제공하며, ChatGPT나 Google Bard와 같은 도구도 개념 이해에 도움이 될 수 있습니다.
❇️ 코드를 바로 작성하기보다는 먼저 화이트보드에 해결 방법을 설계하고 충분히 생각해보는 것이 좋습니다. 의사 코드를 사용하여 아이디어를 정리하는 것도 유용한 방법입니다.
결론
이 글에서는 몇 가지 널리 사용되는 정렬 알고리즘을 살펴보았습니다. 이러한 알고리즘을 모두 처음부터 배우는 것은 어려울 수 있으므로, 하나의 정보 출처에만 의존하기보다는 다양한 자료를 함께 참고하는 것이 좋습니다. 즐거운 코딩 학습 되시길 바랍니다!
다음으로는 Python의 정렬 함수를 이해하는 시간을 가져보시기 바랍니다.