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

검색

자료구조 내에 특정항목을 찾는일

 

선형 검색 ( 배열이 정렬되어있던, 안되어있던 상관 x)

 

배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작

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

// 배열 내에 n이 존재하는지 선형탐색

시간 복잡도가 O(n) 

 

 

이진 검색 (배열이 정렬되어있어야함)

 

중간값을 이용하는 방법인데 첫 인덱스랑 끝 인덱스의 반을 찾으려는 값과 비교하고, 작으면 작은쪽에서 다시 중간값을 찾아서 비교하고, 크면 큰쪽에서 다시 중간값을 찾아 비교하는 방법이다. 

function binarySearch(array, n) {
  let lowIndex = 0, highIndex = array.length-1;

  while(lowIndex <= highIndex) {
    let midIndex = Math.floor((highIndex+lowIndex) / 2);
    if(array[midIndex] === n) {
      return midIndex;
    } else if(n>array[midIndex]) {
      lowIndex = midIndex;
    } else {
      highIndex = midIndex;
    }
  }

  return -1;
}

 

 

 

정렬

거품 정렬 ( = 버블정렬) // 제일 안좋은 정렬임...최악

전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두항목을 교환 한다.( 이것을 계속 반복)

O(n^2)

 

선택 정렬  // 버블정렬 보다 살짝 나음

가장 작은 항목을 찾아서 해당 항목을 배열의 현 위치에 삽입하는 방식

O(n^2)

 

삽입 정렬 // 선택정렬과 비슷

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

O(n^2)

 

퀵 정렬 (빠른정렬) 

기준점을 획득한 다음 해당 기준점을 기준으로 배열을 나눈다

(한쪽에는 기준점보다 큰 항목들이 위치하고 다른 쪽에는 기준점보다 작은 항목들이 위치한다.)

모든 항목이정렬될때까지 과정 반복

평균 : O(nlogn) / 최악 : O(n^2)

 

function quickSort(items) {
  return quickSortHepler(items, 0, tiems.length - 1);
}

function quickSortHepler(items, left, right) {
  let index;
  if (items.length > 1) {
    index = partition(items, left, right);
    if (left < index - 1) {
      quickSortHepler(items, left, index - 1);
    }

    if (index < right) {
      quickSortHepler(items, index, right);
    }
  }
  return items;
}

function partition(array, left, right) {
  let pivot = array[Math.floor((right + left) / 2)];
  while (left <= right) {
    while (pivot > array[left]) {
      left++;
    }
    while (pivot < array[right]) {
      right--;
    }
    if (left <= right) {
      let temp = array[left];
      array[left] = array[right];
      array[right] = temp;
      left++;
      right--;
    }
  }
  return left;
}

 

 

빠른 선택

정렬되지 않은 목록에서 k 번째로 작은 항목을 찾는 선택 알고리즘

빠른 정렬과 같은 접근법을 사용한다.

기준점을 선택한 다음 배열을 분할한다. 하지만, 퀵소트 처럼 기준점의 양쪽 모두를 재귀적으로 수행하는 대신 한쪽만을 재귀적으로 수행한다. 

O(n)

 

 

병합 정렬

하위 배열에 하나의 항목이 존재할 때까지 배열을 하위 배열로 나눈다.

그러고 나서 각 하위배열을 정렬된 순서로 연결(병합)한다.

function merge(leftA, rightA) {
  let 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++]);
    }
  }
  let leftRemains = leftA.slice(leftIndex);
  let rightRemains = rightA.slice(rightIndex);

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

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }

  let midpoint = Math.floor(array.length / 2),
    leftArray = array.slice(0, midpoint),
    rightArray = array.slice(midpoint);

  return merge(mergeSort(leftArray), mergeSort(rightArray));
}

O(nlogn)

 

 

계수정렬 (제한된 범위의 정수를 정렬할때에 계수 정렬을 사용한다) , 가장 빠르지만 제약조건으로 배열의 값 범위를 알아야한다!

항목의 등장횟수를 센다

등장 횟수를 이용하여 새로운 배열을 생성할 수 있다.

O(k+n)

 

 

자바스크립트에는 내장 정렬인 sort()함수가 있다.