TypeScript: Bubble Sort (거품 정렬)

TypeScript

Typed JavaScript at Any Scale.

# TypeScript 1일차

언어를 공부할 때 정렬 알고리즘부터 시작하는 편이다.

Go언어, Python type hinting 버전과 비슷한 느낌이지만,

interface, JS 기능들이 많이 미숙하기에 공부가 더 필요

 

1. 문법 소개

one-line swapping (한 줄로 값 변경)

특이하게, array안에 넣어서 해야한다.

(함수에서 두가지를 return 할 때도 return [a, b]로 쓸 수도 있다.

[array[i], array[i + 1]] = [array[i + 1], array[i]];

 

for-loop

for...of도 있지만, index를 알아야해서 기본 for문 이용

for (let j = 0; j < array.length; j++) {
    // Do something
  }
}

 

2. Bubble Sort

모듈로 내보낼 때는 export를 사용하면 되는 것 같다.

export function bubbleSort(array: number[]): number[] {
  let isSorted: boolean = false;
  const n: number = array.length - 1;  // length 한번만 계산
  let count: number = 0;  // 항상 끝엔 max 값이 있음

  while (!isSorted) {
    isSorted = true;
    for (let j = 0; j < n - count; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
        isSorted = false;
      }
    }
    count++;
  }
  return array;
}

 

3. Jest 테스트

jest bubbleSort.test.ts

import { bubbleSort } from './bubbleSort';

// ES6+ 랜덤 배열 생성 (-5000 <= A[n] <= 5000)
const array: Array<number> = Array.from({length: 5000}, () => Math.floor(Math.random() * 10001) - 5000);

/*
[
      1390, 4361, 4415, 1267, 2556, 4391,  747, 3539, 4455, 1918,
      3548, 3986, 2131, 3349, 3033, 2940, 4772,  368, 4101, 1596,
      3140,  405, 2038, 4841, 2106,  516, 4270,   32, 2419, 3939,
      4558, 2594, 4717, 1623,   26,  205, 2993, 1552, 3804,  410,
      2905,  459,  191, 2323, 4990, 1359,  165,  207, 1077, 1534,
      1895,  191, 4937,  430, 2673, 1731, 4157, 1862, 2765, 2605,
       648, 4384, 3536, 1201, 4410, 1043, 1683, 1314, 1998, 1399,
      2065, 3056, 1660,  473, 3418, 3378,   75, 3603, 1611, 4576,
      3445, 4444, 3130,  330, 1216, 3105, 4717, 1934, 1946, 4245,
      4450, 4343, 2496, 1890, 1748,  129,  472, 4991, 2178, 3423,
      ... 4900 more items
    ]
*/

// 정렬된 배열
const array1: Array<number> = Array.from({length: 5000});

function isSorted(array: Array<number>): boolean {
    for (let i = 1; i < array.length; i++) {
      if (array[i - 1] > array[i]) {
        return false;
      }
    }
    return true;
}

test('random 1', () => {
  expect(isSorted(bubbleSort(array)))
    .toEqual(true);
});  // 약 54ms

test('sorted 1', () => {
  expect(isSorted(bubbleSort(array1)))
    .toEqual(true);
});  // 약 1ms

 

뭔데 이렇게 빠르지

크기 5000 랜덤 배열 정렬: 약 0.054초  (파이썬: 약 2.5초)