[TOC]

1. 개요

요전부터 계속 일만 하다보니 물몸이 되어버려서 근래 다시 쇠질을 시작하기로 했다.

정말 간만에 스쿼트랙 앞에 섰는데....

와!~~ 시부레 악마같은 인간들 진심 정성들여서 섞어놨구나!!!.

..

이렇게 된 이상........

2. 네녀석 들에게 정렬 알고리즘을 알려주마!

진심으로 이사람들에게 정렬 알고리즘을 알려주고 싶어서 만들어 보았다. ㅋㅋ

이것저것 눌러보고 작동시켜 보자. (주의! 무서운 소리가 나므로 밤중에 작동주의!. ㅋㅋㅋㅋ)

2-1. 타입과 데이터 선언

일단 정렬벡터 타입을 선언하고 (범용성을 위한 인터페이스)

type SortableType = {
  /** 데이터 길이 */
  length: Function0<number>
  /** n1, n2 번째 데이터의 비교 같으면 0, n1 이 크면 1, n2 가 크면 -1  */
  compare: Function2<number, number, number>
  /** n1, n2 번째 데이터의 위치를 서로 바꾼다  */
  swap: Function2<number, number, void>
  /** 데이터 shift 연산 */
  shift: Function2<number, number, void>
  /** 데이터 반환 (선택구현) */
  data?: Function0<any>,
  /** 상황별 중간삽입 프로세스 (선택구현) */
  intercept?: InterceptType
}

단순배열 정렬벡터를 구현한다. (javascript array 를 정렬백터 인터페이스로 구현)

class SortableArray<T extends ComparableType> implements SortableType {
  /** 데이터 */
  private _data: Array<T> = undefined as any as Array<T>
  /** 중간삽입 프로세스 */
  private _intercept: InterceptType = undefined as any as InterceptType
  /** 생성자, 데이터와 중간삽입 프로세스를 받는다  */
  constructor(data: Array<T>, intercept?: InterceptType) {
    this._data = data
    if (intercept) { this._intercept = intercept }
  }
  length() { return this._data.length }
  /** 퍼포먼스 향상을 위해 각종 체크 등을 삭제할 수 있다. */
  compare(inx1: number, inx2: number) {
    let v1 = this._data[inx1]
    let v2 = this._data[inx2]
    if (this._intercept) { this._intercept('compare', inx1, inx2) }
    if (v1 == v2 && (v1 === undefined || v1 === null)) { return 0 }
    if (v1 === undefined || v1 === null) { return -1 }
    if (v2 === undefined || v2 === null) { return 1 }
    if (typeof v1 !== typeof v2) { return -1 }
    switch (typeof v1) {
    /** 데이터가 숫자인경우 */
    case 'number': {
      if (v1 === v2) {
        return 0
      } else if (Number(v1) > Number(v2)) {
        return 1
      } else {
        return -1
      }
    } break
    /** 데이터가 문자인경우 */
    case 'string': {
      if (v1 === v2) {
        return 0
      } else if (String(v1) > String(v2)) {
        return 1
      } else {
        return -1
      }
    } break
    /** 데이터가 객체인경우 */
    default: {
      console.log('V1:', v1)
      return v1.compare(v2)
    } }
    return 0
  }
  swap(inx1: number, inx2: number) {
    if (this._intercept) { this._intercept('swap', inx1, inx2) }
    if (inx1 >= 0 && inx2 >= 0 && inx1 < this.length() && inx2 < this.length()) {
      const v = this._data[inx1]
      this._data[inx1] = this._data[inx2]
      this._data[inx2] = v
    }
  }
  shift(inx: number, length: number) {
    if (this._intercept) { this._intercept('shift', inx, length) }
    if (inx >= 0 && length >= 0 && (inx + length) < this.length()) {
      const v = this._data[inx]
      this._data.splice(inx, 1)
      this._data.splice(inx + length, 0, v)
    }
  }
  data() { return this._data }
  intercept(type: string, ...arg: any) {
    if (this._intercept) { this._intercept(type, ...arg) }
  }
}

2-2. 거품정렬 (Bubble sort)

바로 옆자리 데이터끼리만 비교 및 교환한다.
비교횟수, 교환횟수 모두 높다
시간 복잡도는 O(n^2)

const bubblesort: SorterType = (sortable: SortableType, ascending: boolean = true) => {
  if (sortable.intercept) { sortable.intercept('start') }
  let len = sortable.length()
  let complete
  do {
    complete = true
    len -= 1
    for (let inx = 0; inx < len; inx++) {
      /** 바로 옆자리 데이터와 비교 */
      const comp = sortable.compare(inx, inx + 1)
      if ((ascending && comp > 0) || (!ascending && comp < 0)) {
        sortable.swap(inx, inx + 1)
        complete = false
      }
    }
    if (sortable.intercept) { sortable.intercept('complete', complete) }
  } while (!complete)
}

2-3. 선택정렬 (Selection sort)

n번째 자료를 기준으로 두고 그 이후 전체 데이터와 각각 비교 및 교환한다.
비교횟수, 교환횟수 모두 높다
시간 복잡도는 O(n^2)

const selectionsort: SorterType = (sortable: SortableType, ascending: boolean = true) => {
  if (sortable.intercept) { sortable.intercept('start') }
  let len = sortable.length()
  let end = len - 1
  for (let inx1 = 0; inx1 < end; inx1++) {
    for (let inx2 = inx1 + 1; inx2 < len; inx2++) {
      /** n번째 데이터 를 나머지 n번째 이후 전체 데이터와 각각 비교한다  */
      let comp = sortable.compare(inx1, inx2)
      if ((ascending && comp > 0) || (!ascending && comp < 0)) {
        sortable.swap(inx1, inx2)
      }
    }
  }
  if (sortable.intercept) { sortable.intercept('complete') }
}

2-4. 힙정렬 (Heap sort)

2진트리 의 한 종류인 힙트리 를 구성하고 최상위 노드에 신규 데이터를 입력하여 정렬
비교횟수는 적으나 힙트리 유지에 데이터 교환 연산이 많이 일어난다
시간 복잡도는 O(n log n)

힙정렬은 고정데이터가 아닌 연속적인 스트리밍 데이터의 정렬에 더 효과적이다

const heapsort: SorterType = (sortable: SortableType, ascending: boolean = true) => {
  /** 힙트리 생성 */
  const _make_heap = (sortable: SortableType, top: number, size: number, ascending: boolean) => {
    let pos = size >> 1
    /** make heap tree from base of the tree */
    for (let inx = pos; inx >= top + 1; inx--) {
      _heapify(sortable, inx, pos, size, ascending)
    }
  }
  /** 힙트리 정렬 */
  const _heapify = (sortable: SortableType, inx: number, pos: number, size: number, ascending: boolean) => {
    pos = pos + 1
    let is_bin = false
    let child: number
    let comp: number
    while (inx < pos) {
      let parent = inx - 1
      /** top * 2 */
      let child1 = (inx << 1) - 1
      /** top * 2 + 1 */
      let child2 = child1 + 1
      if (child2 < size) {
        comp = sortable.compare(child1, child2)
        if ((ascending && comp > 0) || (!ascending && comp < 0)) {
          child = child1
        } else {
          child = child2
        }
      } else {
        child = child1
      }
      comp = sortable.compare(parent, child)

      if ((ascending && comp < 0) || (!ascending && comp > 0)) {
        sortable.swap(parent, child)
        is_bin = true
        inx = child + 1
      } else {
        break
      }
    }
    return is_bin
  }
  {
    let pos: number
    let size = sortable.length()
    /** 최초 힙트리를 정렬한다. */
    _make_heap(sortable, 0, size, ascending)
    while (size > 1) {
      size -= 1
      pos = size >> 1
      /** 최상위 노드를 완료로 보내고 최하위 노드를 최상위 로 보낸다  */
      sortable.swap(0, size)
      /** 다시 힙트리를 정렬한다 */
      _heapify(sortable, 1, pos, size, ascending)
    }
  }
}

2-5. 퀵정렬 (Quick sort)

데이터를 절반으로 나누어 기준점 기준으로 왼쪽, 오른쪽으로 분할해 정렬
비교횟수, 교환횟수 모두 최저. 가장 빠르다.
시간 복잡도는 O(n log n)

const quicksort: SorterType = (sortable: SortableType, ascending: boolean = true) => {
  const _quicksort = (sortable: SortableType, left: number, right: number, ascending: boolean) => {
    let diff = right - left
    let comp
    if (diff == 1) {
      comp = sortable.compare(left, right)
      if ((ascending && comp > 0) || (!ascending && comp < 0)) {
        sortable.swap(left, right)
      }
    } else if (diff > 1) {
      let linx = left
      let rinx = right
      let pivot = (left + right) >> 1
      /** 절반으로 나누어(pivot) 왼쪽과 오른쪽을 정렬한다. */
      LOOP1: do {
        LOOP2: do {
          comp = sortable.compare(linx, pivot);
          if ((ascending && comp < 0) || (!ascending && comp > 0)) {
            linx += 1
          } else {
            break LOOP2
          }
        } while(true)
        LOOP3: do {
          comp = sortable.compare(rinx, pivot)
          if ((ascending && comp > 0) || (!ascending && comp < 0)) {
            rinx -= 1
          } else {
            break LOOP3
          }
        } while(true)
        if (linx <= rinx) {
          if (linx != rinx) {
            if (linx == pivot) {
              pivot = rinx
            } else if (rinx == pivot) {
              pivot = linx
            }
            sortable.swap(linx, rinx)
          }
          linx += 1
          rinx -= 1
        }
        if (linx > rinx) { break LOOP1 }
      } while(true)
      if (left < rinx) { _quicksort(sortable, left, rinx, ascending) }
      if (linx < right) { _quicksort(sortable, linx, right, ascending) }
    }
  }
  let len = sortable.length()
  if (sortable.intercept) { sortable.intercept('start') }
  _quicksort(sortable, 0, len - 1, ascending)
  if (sortable.intercept) { sortable.intercept('complete') }
}

3. 기타

급작스럽게 정렬 알고리즘이 생각나서 다시한번 상기시켜 보며 가시화 시켜 보았다.

selection sort 같은알고리즘은 특히나 가시화 된 자료를 보면서 개선시킬 포인트가 보이기도 했다.

뭐.. 여튼 재미삼아 만들어본 프로젝트 되시겠다. ㅋㅋ

SortableType 인터페이스를 일부러 만들어서 범용성을 극대화 시켰다.

나중에 이거 기반으로 교육용 검색엔진도 한번 재미삼아 만들어 볼 생각이다.

GIT 주소는 아래와 같다

https://github.com/lupfeliz/algorhithm-visualizer
https://gitlab.ntiple.com/developers/algorhithm-visualizer