191103_TIL(Search & Sort in JS)

자바스트립트 검색과 정렬

검색과 정렬의 정의

검색

자료를 얻기 위해 자료구조의 항목들을 반복적으로 접근하는 것.

정렬

자료구조의 항목들을 순서대로 위치시는 것.

배열이 정렬됐는지 여부에 따른 검색 기법 두 가지

선형검색

정렬되지 않은 자료와 정렬된 자료 모두 사용 가능하기 때문에 유연하다.

최악의 경우 전체 배열을 순회해야 하기 때문에 시간 복잡도는 O(n)이다.

배열의 모든 항목을 확인해야 한다.

배열이 정렬되지 않은 경우에 선형 검색을 사용해야 한다.

이진검색

정렬된 자료에 대해 사용. 시간 복잡도가 선형 검색의 시간 복잡도보다 낮은 장점이 있다.

중간 값을 확인하여 원하는 값보다 중간 값이 큰지 작은지 확인하여 큰 경우 중간 값보다 큰 쪽을 검색하고 작은 경우 중간 값보다 작은 쪽만 검색한다.

이진 검색 알고리즘은 배열을 계속해서 두 부분으로 나눈다.

// 이진 검색 알고리즘 구현
// 중간 값이 검색 값과 일치하는지 확인하고 검색 값이 중간 값보다 큰 경우 검색 범위의 하한값을 중간값에 1을 더한 값으로 설정하고 검색 값이 중간 값보다 작은 경우 검색 범위의 상한값을 중간값에 1을 뺀 값으로 설정한다.
function binarySearch(array, n) {
    var lowIndex = 0, highIndex = array.length-1;
    
    while(lowIndex <= highIndex) {
        var midIndex = Math.floor((highIndex+lowIndex) / 2);
        if(array[midIndex] == n) {
            return midIndex;
        } else if(n>array[midIndex]) {
            lowIndex = midIndex+1;
        } else {
            highIndex = midIndex-1;
        }
    }
    return -1;
}

console.log(binarySearch([1,2,3,4], 4)); // 3
console.log(binarySearch([1,2,3,4], 7)); // -1

정렬 알고리즘

거품 정렬(bubble sort)

거품 정렬은 가장 간단한 정렬 알고리즘이다. 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다.

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

거품 정렬은 최악의 시간 복잡도를 지닌 정렬이다. 다른 정렬 알고리즘은 배열의 이미 정렬된 부분을 활용하는데 비해 거품 정렬은 모든 가능한짝을 비교하기 때문이다.

시간 복잡도 : O(n^2)

선택 정렬(selection sort)

가장 작은 항목을 찾아서 해당 항목을 배열의 현 위치에 삽입하는 방식으로 동작한다. 거품 정렬보다는 조금 더 나은 퍼포먼스를 보이지만 선택 정렬 역시 시간 복잡도는 O(n^2)이다.

function swap(array, index1, index2) {
  var temp = array[index1];
  array[index1] = array[index2];
  array[index2] = temp;
}

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;
          }
      }
      // 현재 위치가 가장 작은 원소가 아니라면 원소들을 교환한다.
      if (i != min) {
          swap(items, i, min);
      }
  }

  return items;
}

삽입 정렬(insertion sort)

삽입 정렬은 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다.

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--) {
          items[j + 1] = items[j];
      }
      items[j + 1] = value;
  }
  return items;
}

외부 for 루프는 배열 인덱스를 순회하고 내부 for 루프는 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다.

시간 복잡도 : O(n^2)

빠른 정렬(quick sort)

빠른 정렬은 기준점을 획득한 다음 해당 기준점을 기준으로 배열을 나눈다. 모든 항목이 정렬될 때까지 이 과정을 거친다. 가장 이상적인 기준점은 배열의 중간 값이다. 하지만 정렬되지 않은 배열의 중간 값을 얻기 위해서는 선형 시간이 걸린다. 따라서 일반적으로 분할 부분의 첫 번째 항목과 중간 항목, 마지막 항목의 중간 값을 취해 기준점을 얻는다.

시간복잡도 : 평균 O(nlogn), 최악의 경우 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;
}

병합 정렬(merge sort)

병합 정렬은 각 하위 배열에 하나의 항목이 존재할 때까지 배열을 하위 배열로 나눈다. 그리고 나서 각 하위 배열을 정렬된 순서로 연결(병합)한다.

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));
}

merge 함수는 두 배열을 가지고 하나의 결과 배열로 병합한다. 순서를 지키기위해 배열을 병합하면서 배열의 항목들을 비교해야 한다. mergesort 함수는 큰 배열을 두 개의 개별적인 배열로 분할한 다음 재귀적으로 merge를 호출한다.

안정적인 정렬이 필요한 경우에 병합 정렬을 사용한다. 안정적인 정렬은 동일한 값을 지닌 항목들의 순서가 바뀌지 않음을 보장하는 정렬이다. ex) [7,3,2,6,9,7] 배열에는 7이 두 개 존재한다. 첫번째는 7(1), 두번째를 7(2)라고 하였을 때 안정적인 정렬은 이 순서를 항상 보장한다.

시간복잡도 : O(nlogn)

계수 정렬(count sort)

계수 정렬은 갑들을 비교하지 않기 때문에 O(k+n)시간 안에 수행된다. 숫자에 대해서만 동작하며 특정 범위가 주어져야 한다는 한계가 있다. 배열의 각 항목의 등장 횟수를 센다. 해당 등장 횟수를 사용해 새로운 배열을 생성할 수 있다. 계수 정렬은 항목들을 교환하지 않고도 자료를 정렬한다.

제한된 범위의 정수를 정렬할 때는 계수 정렬이 가장 빠른 정렬이다.

function countSort(array) {
  var hash = {},
      countArr = [];
  for (var i = 0; i < array.length; i++) {
      if (!hash[array[i]]) {
          hash[array[i]] = 1;
      } else {
          hash[array[i]]++;
      }
  }

  for (var key in hash) {
      // 항목이 몇개가 되든 해당 항목을 배열에 추가한다.
      for (var i = 0; i < hash[key]; i++) {
          countArr.push(parseInt(key));
      }
  }

  return countArr;
}

자바스크립트 내장 정렬

자바스크립트네는 배열 객체에 사용 가능한 내장 메소드인 sort()가 있다. sort()는 항목들을 오름차순으로 정렬한다. 필요한 경우 sort() 함수 호출 시 비교 함수를 sort() 함수의 매개변수로 전달할 수 있다.

기본 비교 함수는 배열을 알파벳 순으로 정렬한다. 따라서 기본 비교 함수는 숫자 자료에 대해서는 제대로 동작하지 않는다.

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

위 결과가 나오는 이유는 자바스크립트가 항목들을 문자열로 변환한 다음, 항목들을 알파벳 순으로 정렬했기 때문이다.

// 숫자 오름차순 정렬
var array = [12,4,3,1,2,23,34];

function comparatorNumber(a,b) {
    return a - b;
}

array.sort(comparatorNumber); // [1,2,3,4,12,23,34]