essential
essential

1. ArrangeArray

배열 정렬하기, 제약조건의 중요성과 sort 메서드 이해하기

algorithm test

01. ArrangeArray

Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.108.


Problem solving

제약조건을 보면 데이터 개수는 최대 105 입니다. 만약 정수 배열의 최대 길이가 10이라면 O(N2)알고리즘을 사용해도 됩니다. 단순히 O(N2) 정렬 알고리즘으로 정렬하면 이 문제는 통과할 수 없다.


① catch point : 시간 복잡도를 고려하라!

버블정렬로 해당 문제를 풀어보자

function bubblesort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - 1; j++) {
      if (arr[j + 1] < arr[j]) {
        const tmp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = tmp;
      }
    }
  }
  return arr;
}

function measureTime(callback, arr) {
  const start = Date.now();
  const result = callback(arr);
  const end = Date.now();
  return [end - start, result];
}

const arr = Array.from({ length: 10000 }, (_, k) => 10000 - k);

const [bubbleTime, bubbleResult] = measureTime(bubblesort, arr);
console.log(`첫번째 코드 실행시간: ${bubbleTime}ms`);
// 첫 번째 코드 시간 측정
// 첫 번째 코드 실행 시간: 2081ms


sort( ) 메서드를 사용하여 풀면

function solution(arr) {
  arr.sort((a, b) => a - b);
  return arr;
}

const arr = Array.from({ length: 10000 }, (_, k) => 10000 - k);

const [bubbleTime, bubbleResult] = measureTime(bubblesort, arr);
console.log(`첫번째 코드 실행시간: ${bubbleTime}ms`);
// 두 번째 코드 시간 측정
// 두 번째 코드 실행 시간: 1ms


② catch point : sort 메서드를 이해해보자!

sort 메서드는 배열의 요소를 정렬한다. 원본 배열을 직접 변경하여 정렬된 배열을 반환한다.

const fruits = ['Banana', 'Orange', 'Apple'];

fruits.sort(); // 오름차순(ascending)으로 정렬

console.log(fruits); // ['Apple', 'Banana', 'Orange'] sort 메서드는 원본배열을 직접변경

fruits.reverse() // 내림차순(descending)으로 정렬

console.log(fruits)l // ['Orange', 'Banana', 'Apple'] reverse 메서드도 원본배열을 직접변경

하지만, 숫자로 이루어진 배열을 정렬할 때는 주의가 필요하다!

const points = [40, 100, 1, 5, 2, 25, 10];

points.sort();

console.log(points); // [1, 10, 100, 2, 25, 40, 5]

sort 메서드의 기본 정렬 순서는 유니 코드 포인트의 순서를 따른다. 배열의 요소가 숫자 타입이라 할 지라도 배열의 요소를 일시적으로 문자열로 변환한 후 유니코드 포인트의 순서를 기준으로 정렬한다. 

['2', '1'].sort(); // ["1", "2"]
[2, 1].sort(); // [1, 2]

['2', '10'].sort(); // ["10", "2"]
[2, 10].sort(); // [10, 2]

예를 들어,

문자열 ‘1’의 유니코드 포인트는 U+0031

문자열 ‘2’의 유니코드 코드 포인트는 U+0032다.

문자열 ‘10’의 유니코드 코드 포인트는 U+0031U+0030이다.

따라서 문자열 배열 [‘2’, ‘10’]을 sort 메서드로 정렬하면 문자열 ‘10’의 유니코드 코드 포인트 U+0031U+0030이 문자열 ‘2’의 유니코드 코드 포인트 U+0032보다 앞서므로 [‘10’, ‘2’]로 정렬된다.

따라서 숫자 요소를 정렬할 때 sort 메서드는 정렬 순서를 정의하는 비교함수를 인수로 전달해야 한다.
비교함수는 양수나 음수 또는 0을 반환해야 한다.
비교함수의 반환값이 0보다 작으면 비교함수의 첫 뺀재 인수를 우선하여 정렬하고, 0이면 정렬하지 않으며, 0보다 크면 두 번째 인수를 우선하여 정렬한다.

const points = [40, 100, 1, 5, 2, 25, 10];

points.sort((a, b) => a - b);
console.log(points); // [1, 2, 5, 10, 25, 40, 100]

points.sort((a, b) => b - a);
console.log(points); // [100, 40, 25, 10, 5, 2, 1]


🚀 plus) 객체를 요소로 갖는 배열을 정렬하는 예제
const todos = [
  { id: 4, content: 'Javascript' },
  { id: 1, content: 'HTML' },
  { id: 2, content: 'CSS' },
];

function compare(key) {
  return (a, b) => (a[key] > b[key] ? 1 : (a[key] < b[key] ? -1 : 0));
}

todos.sort(compare('id')); // sort 메서드에 비교함수를 인자로 전달
console.log(todos);
/*
[
  { id: 1, content: 'HTML' },
  { id: 2, content: 'CSS' },
  { id: 4, content: 'Javascript' }
]
*/


Q. Array.prototype.sort 함수는 O(n2) 시간복잡도를 갖진 않을까?

sort메서드는 Quicksort 알고리즘을 사용했었다. Quicksort알고리즘은 동일한 값의 요소가 중복되어 있을 때 초기 순서와 변경 될 수 있는 불안정한 정렬 알고리즘으로 알려져있다.
ECMAScript 2019(ES10)에서 sort 메서드는 Timesort알고리즘을 사용하도록 바뀌게 되면서
최악의 경우에도 O(NlogN) 시간 복잡도를 유지한다.



Development
Algorithm