자바스크립트로 하는 자료구조와 알고리즘 - 10장. 검색과 정렬

10장. 검색과 정렬

검색 (search)

- 검색은 자료 구조 내에 특정 항목을 찾는 일을 말하며, 배열이 정렬됐는지 여부에따라 두 가지 주요 기법이 있다.

선형 검색

• 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작한다.
• 시간 복잡도 : O(n)
• 배열의 정렬 여부와는 관계없이 동작하기때문에 좋으므로 정렬되지 않은 배열을 검색하기 좋다.

function linearSearch(arr, n) {
    for(var i = 0; i < arr.length; i++){
        if (arr[i] == n) return true;
    }
    return false;
}

이진 검색 (탐색)

• 중간 값을 확인해서 원하는 값보다 중간 값이 작은지 큰지를 확인하면서 동작한다.
• 시간 복잡도: O(logn)
• 이진 탐색은 빠르지만 배열이 정렬된 경우에만 사용할 수 있다.

function binarySearch(arr, n) {
    var lowIdx = 0, highIdx = arr.length - 1;

    while (lowIdx <= highIdx) {
        var midIdx = Math.floor((highIdx + lowIdx) / 2);
        if (arr[midIdx] == n) return arr[midIdx];
        else if (n>arr[midIdx]) lowIdx = midIdx;
        else highIdx = midIdx;
    }
    return -1;
}

정렬 (sort)

거품 정렬 (bubble sort)

• 가장 간단한 알고리즘으로, 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다.
• 시간 복잡도: O(n^2) (중첩 루프)
• 거품 정렬은 모든 가능한 짝을 비교하기 때문에 최악의 정렬이라 할 수 있다.

function bubbleSort(array) {
  for (var i = 0, arrayLength = array.length; i < arrayLength; i++) {
    for (var j = 0; j <= i; j++) {
      if (array[i] < array[j]) {
        swap(array, i, j);
      }
    }
  }
  return array;
}

책의 예시는 인접 두 항목을 교환하는 코드가 아니어서 제로초님의 블로그글을 참고하여 공부하였다.

function bubbleSort(array) {
  for (var i = 0, arrayLength = array.length; i < arrayLength - 1; i++) {
    for (var j = 0; j < arrayLength - 1 - i; j++) {
      if (array[j] > array[j+1]) { // 인접항목 교환
        swap(array, j, j+1);
      }
    }
  }
  return array;
}

선택 정렬 (selection sort)

• 가장 작은 항목을 찾아서 해당 항목을 배열의 현 위치에 삽입한다.
• 시간 복잡도 : O(n^2) (중첩 루프)

function selectionSort(items) {
  var len = items.length, min;

  for (var i = 0; i < len; i++) {
    min = i;
    for (j = i+1; j < len; j++) { 
      if (items[j] < items[min]) {
        min = j; // 최솟값의 위치를 min값에 할당
      }
    }
    if (i != min) { // 현재 위치가 최솟값의 위치가 아니면 교환
      swap(items, i, min);
    }
  }
  return items;
}

삽입 정렬 (insertion sort)

• 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다.
• 시간 복잡도 : O(n^2) (중첩 루프)

function insertionSort(items) {
  var len = items.length, value, i, j;
  
  for (i=0; i < len; i++) {
    value = items[i]; // 현재 값 덮어써질수 있으므로 저장함

    for (j = i-1; j > -1 && items[j] > value; j--) { // value가 검사값보다 작다면 검사값 위치 +1
      items[j+1] = items[j];
    } // j는 검사값이 크지 않을 때 까지 감소한다.
    items[j+1] = value; // 감소한 j값 +1이 value의 위치(가장 작은값)
    console.log(items);
  }
  return items;
}

빠른 정렬 (quick sort)

• 기준점을 획득한 다음 해당 기준점을 기준으로 왼쪽은 작은 항목, 오른쪽은 큰 항목으로 배열을 나눈다.
• 시간복잡도: 평균 - O(nlog_2(n)), 최악 - O(n^2)
• 기준점을 항상 잘못 선택하는 경우는 시간 복잡도가 O(n^2)이 될 수 있다.

function quickSort(items) {
  return quickSortHelper(items, 0, items.length - 1);
}
function quickSortHelper(items, left, right) {
  var index;
  if (items.length > 1) {
    index = partition(items, left, right);

    if (left < index - 1) { // 기준점 왼쪽 빠른정렬
      quickSortHelper(items, left, index - 1);
    }
    if (index < right) { // 기준점 오른쪽 빠른정렬
      quickSortHelper(items, index, right);
    }
  }
  return items;
}
function partition(array, left, right) { // 기준점 중앙으로
  var pivot = array[Math.floor((right + left) / 2)];
  while (left <= right) {
    while (pivot > array[left]) {
      left++;
    }
    while (pivot < array[right]) {
      right--;
    }
    if (left <= right) {
      var temp = array[left];
      array[left] = array[right];
      array[right] = temp;
      left++;
      right--;
    }
  }
  return left;
}

빠른 선택 (quick select)

• 정렬되지 않은 목록에서 k번째로 작은 항목을 찾는 선택 알고리즘이다.
• 빠른 정렬과 같은 접근법을 사용하지만, 기준점의 양쪽 모두를 재귀적으로 수행하는 대신 한쪽만을 재귀적으로 수행한다는 차이점이있다.
• 이로인해 복잡도는 O(nlog_2(n))에서 O(n)으로 낮아진다.
• 시간복잡도: O(n)

function quickSelectInPlace(A, l, h, k) {
  var p = partition(A, l, h);
  if (p == (k-1)) {
    return A[p]; // 일치하면 값 return
  } else if (p > (k-1)) {
    return quickSelectInPlace(A, l, p-1, k); // pivot 왼쪽배열 재귀
  } else {
    return quickSelectInPlace(A, p+1, h, k); // pivot 오른쪽배열 재귀
  }
}

병합 정렬 (merge sort)

• 각 하위 배열에 하나의 항목이 존재할 때까지 배열을 하위 배열로 나눈 다음, 각 하위 배열을 정렬된 순서로 병합한다.
• 시간복잡도: O(nlog_2(n)), 공간복잡도: O(n)
• 병합 정렬은 O(n)의 공간을 사용한다는 단점이 있다.
• 왼쪽, 오른쪽의 두 배열을 가지고 하나의 결과 배열로 병합한다. (아래의 merge 함수)

function merge(leftA, rightA) { // 병합 함수
  var results = [], leftIndex = 0, rightIndex = 0;

  while (leftIndex < leftA.length && rightIndex < rightA.length) {
    if (leftA[leftIndex] < rightA[rightIndex]) {
      results.push(leftA[leftIndex++]);
    } else {
      results.push(rightA[rightIndex++]);
    }
  }
  var leftRemains = leftA.slice(leftIndex),
  rightRemains = rightA.slice(rightIndex);

  return results.concat(leftRemains.concat(rightRemains));
}

function mergeSort(array) {
  if (array.length<2){
    return array;
  }
  var midpoint = Math.floor((array.length)/2),
  leftArray = array.slice(0, midpoint),
  rightArray = array.slice(midpoint);

  return merge(mergeSort(leftArray), mergeSort(rightArray)); // left와 right로 계속 분할
}

계수 정렬 (count sort)

• 값을 비교하지 않기 때문에 O(k+n)시간 안에 수행된다.
• 숫자에 대해서만 동작하며, 특정 범위가 주어져야 한다.
• 배열의 각 항목의 등장 횟수를 세어 해당 등장 횟수를 사용해서 새로운 배열을 생성한다.
• 주로 제한된 범위의 정수를 정렬할 때 가장 빠른 정렬 방법이기 때문에 계수 정렬을 사용한다.
• 시간복잡도: O(k+n), 공간복잡도: O(k)

function countSort(arr) {
  var hash = {}, countArr = [];
  for (var i=0; i<arr.length; i++) {
    if (!hash[arr[i]]) {
      hash[arr[i]] = 1;
    } else {
      hash[arr[i]]++;
    }
  }
  for (var key in hash) { // 항목이 몇개가 되든 해당 항목을 배열에 추가한다
    for (var i=0; i<hash[key]; i++) {
      countArr.push(parseInt(key)); // key 를 hash[key] 값만큼 arr에 push한다.
    }
  }
  return countArr;
}

자바스크립트 내장 정렬

• 자바스크립트는 배열 객체에 사용 가능한 내장 메소드 sort()가 존재하며, 이는 항목들을 오름차순으로 정리한다.

var arr = [12, 3, 4, 2, 1, 34, 23];
arr.sort(); // [1, 12, 2, 23, 3, 34, 4]

요약

알고리즘	시간 복잡도	공간 복잡도
빠른 정렬(quick sort)	O(nlog_2(n))	O(nlog_2(n))
병합 정렬(merge sort)	O(nlog_2(n))	O(nlog_2(n))
거품 정렬(bubble sort)	O(n^2)	O(n^2)
삽입 정렬(insertion sort)	O(n^2)	O(n^2)
선택 정렬(select sort)	O(n^2)	O(n^2)
계수 정렬(count sort)	O(k+n)	O(k)