[Javascript로 정리하는 이코테] 5. 정렬

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

개념

• 정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
• 정렬 알고리즘은 이진 탐색의 전처리 과정

 

선택 정렬

• 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 맨 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.
• 시간복잡도: O(n^2)

 

예제 6-1. 선택 정렬

let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];

for (let i = 0; i < array.length; i++) {
  let minIdx = i;
  for (let j = i + 1; j < array.length; j++) {
    if (array[minIdx] > array[j]) {
      minIdx = j;
    }
  }
  [array[i], array[minIdx]] = [array[minIdx], array[i]];
}

console.log(array);

 

예제 6-2. 자바스크립트 스와이프(swap)

let array = [3, 5];
[array[0], array[1]] = [array[1], array[0]];

console.log(array); // [5, 3]

 

삽입 정렬

• 특정한 데이터를 적절한 위치에 삽입하는 과정을 반복한다.
• 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
• 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어 있을 때’ 훨씬 효율적이다. 따라서 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 선택 정렬에 비해, 실행 시간 측면에서 더 효율적이다.
• 시간복잡도: O(n^2), 최선의 경우 O(n)

 

예제 6-3. 삽입 정렬

let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];

for (let i = 1; i < array.length; i++) {
  for (let j = i; j > 0; j--) {
    if (array[j - 1] < array[j]) break;
    [array[j], array[j - 1]] = [array[j - 1], array[j]];
  }
}

console.log(array);

 

퀵 정렬

• 기준을 설정하고 큰 수와 작은 수를 교환한 후 배열을 반으로 나누는 방식으로 동작한다.
• 기준을 피벗(pivot)이라 하며, 이를 어떻게 설정한 것인지에 따라 배열을 분할하는 여러 가지 방식이 있다.

 

이 책은 호어 분할 방식을 기준으로 설명한다.

1. 배열의 첫 번째 데이터를 피벗으로 정한다.
2. 배열의 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터는 피벗보다 작은 데이터를 찾는다. 그리고 그 둘을 교환한다.
3. 두 값이 엇갈릴 때까지 2번 과정을 반복한다. 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값이 엇갈리는 경우, 작은 데이터와 피벗의 위치를 서로 변경한다.
4. 이후 배열을 보면 피벗의 왼쪽에는 피벗보다 작은 데이터들이, 오른쪽에는 피벗보다 큰 데이터들이 위치한다. 이러한 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

피벗을 기준으로 좌우 배열 각각에 위의 분할 과정을 반복(배열의 길이가 1이 될 때까지)하면 정렬이 이루어진다. 이는 재귀 함수와 동작 원리가 같다.

 

시간복잡도

• O(nlogn), 최악의 경우 O(n^2)
  • 최선의 경우 배열이 절반씩 분할이 된다면 로그 탐색을 할 수 있다.
  • 하지만 이미 정렬이 되어 있는 경우, 분할을 위해 선형 탐색이 이루어지기 때문에 매우 느리게 동작한다.

 

예제 6-4. 퀵 정렬

let arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8];
const n = arr.length;

const quickSort = (arr, start, end) => {
  if (start >= end) return;

  const p = start;
  let left = start + 1;
  let right = end;

  while (left <= right) {
    //피벗보다 큰 데이터 찾을 때까지 탐색
    while (left <= end && arr[p] >= arr[left]) {
      left++;
    }
    //피벗보다 작은 데이터 찾을 때까지 탐색
    while (right > start && arr[p] <= arr[right]) {
      right--;
    }

    //swap
    if (left > right) {
      [arr[p], arr[right]] = [arr[right], arr[p]];
    } else {
      [arr[left], arr[right]] = [arr[right], arr[left]];
    }
  }

  quickSort(arr, start, right - 1);
  quickSort(arr, right + 1, end);
};

quickSort(arr, 0, n - 1);
console.log(arr);

 

예제 6-5. 자바스크립트의 장점을 살린 퀵 정렬

let arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8];
const n = arr.length;

const quickSort = (arr) => {
  if (arr.length <= 1) return arr;

  const p = arr[0]; //피벗은 첫 번째 원소
  const tail = arr.slice(1); //피벗을 제외한 배열

  const leftArr = tail.filter((v) => v <= p); //분할된 왼쪽 부분 (피벗보다 작은 값)
  const rightArr = tail.filter((v) => v > p); //분할된 오른쪽 부분 (피벗보다 큰 값)

  return [...quickSort(leftArr), p, ...quickSort(rightArr)];
};

console.log(quickSort(arr, 0, n - 1));

 

계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
• 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하다.
• 다만, 공간 복잡도 측면에서 비효율적일 수 있으니 주의해야 한다.
• 시간복잡도: O(n + k)
  • 데이터의 개수 n, 데이터 중 최대값의 크기 k

 

예제 6-6. 계수 정렬

const arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2];

const count = [...Array(Math.max(...arr) + 1).fill(0)];

arr.forEach((num) => count[num]++);

let sorted = '';
for (let num = 0; num < count.length; num++)
  sorted += num.toString().repeat(count[num]);
console.log([...sorted]);

 

자바스크립트의 정렬 라이브러리

• 자바스크립트는 sort() 메서드를 제공한다.
• 일반적으로 시간복잡도 O(nlogn)을 보장한다.
• 기본 정렬 순서는 유니코드 기반이므로, 숫자를 정렬하기 위해서는 아래와 같이 정렬 순서 정의 함수를 설정해야 한다.

const arr = [21, 4, 11, 38, 1, 5];

const sortedUni = arr.sort();
console.log(sortedUni); //[ 1, 11, 21, 38, 4, 5 ]

const sortedNum = arr.sort((a, b) => a - b);
console.log(sortedNum); //[ 1, 4, 5, 11, 21, 38 ]

 

 

실전 문제

위에서 아래로

• sort()를 통해 정렬 → O(nlogn)

const fs = require('fs');
let input = fs.readFileSync('./tc.txt').toString().trim().split('\n');

let [n, ...arr] = input;
arr = arr.map((v) => +v.replace('\r', ''));

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

console.log(solution(n, arr));

 

성적이 낮은 순서로 학생 출력하기

• sort()를 통해 정렬 → O(nlogn)
• 입력의 최대값이 100이므로 O(n)을 보장하는 계수 정렬을 이용해도 된다.

const fs = require('fs');
let input = fs.readFileSync('./tc.txt').toString().trim().split('\n');

let [n, ...arr] = input;
const students = arr.map((v) => v.replace('\r', '').split(' '));

function solution(n, students) {
  const sortedNames = students
    .sort((a, b) => a[1] - b[1])
    .map((student) => student[0]);

  return sortedNames.join(' ');
}

console.log(solution(n, students));

 

두 배열의 원소 교체

• A는 오름차순, B는 내림차순으로 각각 정렬하고
• A의 원소가 B의 원소보다 작을 때, 두 배열의 원소를 교체한다.

const fs = require('fs');
let input = fs.readFileSync('./tc.txt').toString().trim().split('\n');

let [nk, A, B] = input;
const [n, k] = nk.split(' ');
A = A.replace('\r', '')
  .split(' ')
  .map((v) => +v);
B = B.replace('\r', '')
  .split(' ')
  .map((v) => +v);

function solution(n, k, A, B) {
  A.sort((a, b) => a - b);
  B.sort((a, b) => b - a);

  for (let i = 0; i < k; i++) {
    if (A[i] < B[i]) {
      [A[i], B[i]] = [B[i], A[i]];
    }
  }

  return A.reduce((a, b) => a + b);
}

console.log(solution(n, k, A, B));

 

 

Reference

• https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort