자바스크립트로 하는 자료구조와 알고리즘 책을 읽고 공부한 내용을 정리한 글입니다.

검색

선형검색

선형탐색이라고도 함 (search)

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

그냥 0부터 끝까지 검색하는거입니다.

시간복잡도는 O(n) 이겠죵~!

function linearSearch(array,n){
	for(let i=0;i<array.length;i+=1){
    	//찾을 내용 
    }
}

선형검색은 배열의 정렬여부와 상관없이 동작하기 때문에
배열이 정렬되지 않은 경우에는 선형검색을 사용해야 합니다.

이진 검색

이진 검색은 정렬된 자료에 사용할 수 있는 검색 알고리즘입니다.

중간값을 확인해서 원하는 값보다 해당 값이 큰지 작은지 확인합니다.

function binarySearch(array, target, lowIndex, highIndex) {
  const middleIndex = Math.floor((lowIndex + highIndex) / 2);
  if (array[middleIndex] === target) return middleIndex;
  if (array[middleIndex] < target) {
    return binarySearch(array, target, middleIndex + 1, highIndex);
  }
  if (array[middleIndex] > target) {
    return binarySearch(array, target, lowIndex, middleIndex - 1);
  }
}
const array = [1, 2, 3, 4, 5, 6, 7];
const initialHighIndex = array.length;
const initialLowIndex = 0;
const index = binarySearch(array, 7, initialLowIndex, initialHighIndex);
console.log(index);

이진검색은 정렬된 경우에만 사용하여야 합니다

정렬

거품정렬

전체배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다.

function bubbleSort(array) {
  const arrayLength = array.length;
  for (let i = 0; i < arrayLength; i += 1) {
    for (let j = 0; j <= i; j += 1) {
      if (array[j] > array[i]) {
        const temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
  }
}
const array = [1, 31, 4, 2, 123, 45, 2, 3, 4, 5, 7];

bubbleSort(array);
console.log(array);

거품정렬은 최악의 정렬로 매우느립니다.

선택정렬

function selectionSort(array) {
  const arrayLength = array.length;
  for (let i = 0; i < arrayLength; i += 1) {
    let min = array[i];
    let minIndex = i;
    for (let j = i; j <= arrayLength; j += 1) {
      if (array[j] < min) {
        min = array[j];
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      const temp = array[minIndex];
      array[minIndex] = array[i];
      array[i] = temp;
    }
  }
}

삽입 정렬

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

function insertionSort(array) {
  const arrayLength = array.length;
  for (let i = 0; i < arrayLength; i += 1) {
    const value = array[i];
    for (let j = i - 1; j >= 0; j -= 1) {
      if (array[j] > value) {
        array[j + 1] = array[j];
        array[j] = value;
      }
    }
  }
}

버블정렬,선택정렬,삽입정렬 세 개 모두 O(n^2)의 시간복잡도를 가집니다.

퀵 정렬

기준점을 획득한 다음
왼쪽에 기준점보다 작은 숫자를 넘기고
오른쪽에 기준점보다 큰 숫자를 넘긴다.

재귀함수로 구현한다.

left 시작 index
right 끝 index

처음에 배열에서 왼쪽인덱스가 오른쪽 인덱스를 넘지 않을 때까지 반복문을 돌린다. (pivot을 기준으로 왼쪽과 오른쪽을 나눈 것이다.)
나눠진 두 배열에서 조건에 맞는 인덱스를 찾은 후 서로 교환한다 .
다 교환 되었으면 현재 옮겨진 pivotindex를 return 한다.

function quickSort(array, left, right) {
  if (array.length > 1) {
    let pivotIndex = partition(array, left, right);

    if (left < pivotIndex - 1) {
    //왼쪽에서 다시 재귀호출
      quickSort(array, left, pivotIndex - 1);
    }
    if (pivotIndex < right) {
    //오른쪽에서 다시 재귀호출
      quickSort(array, pivotIndex, right);
    }
  }
  return array;
}
function partition(array, left, right) {
 //임의로 만들어진 기준점
  const pivot = array[Math.floor((left + right) / 2)];
 
 //left right 나누기 
  while (left <= right) {
    while (array[left] < pivot) {
    //왼쪽 배열이 원소가 기준점보다 작을경우 정상적이므로 left인덱스를 증가시킨다.
      left += 1;
    }
    while (array[right] > pivot) {
    //오른쪽 배열이 원소가 기준점보다 클 경우 정상적이므로 right인덱스를 감소시킨다.
      right -= 1;
    }
    //둘다 찾아졌을 경우 바꾼다.
    //left>right의 경우 다 바껴진 것이므로 return 
    if (left <= right) {
      const temp = array[left];
      array[left] = array[right];
      array[right] = temp;
      //다음 인덱스 검사
      left += 1;
      right -= 1;
    }
  }
  return left;
}

퀵정렬은 구현하기 어렵지만 O(nlog(n))만큼의 빠르기가 나올 수 있습니다.
다만 최악의경우 O(n^2)입니다.

병합정렬

function merge(left, right) {
  console.log(left, right, "merge");
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex++]);
    } else result.push(right[rightIndex++]);
  }
  const leftRemain = left.slice(leftIndex);
  const rightRemain = right.slice(rightIndex);

  return result.concat(leftRemain).concat(rightRemain);
}
function mergeSort(array) {
  if (array.length < 2) {
    return array; //항목이 하나일 때 return
  }

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

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

const array = [1, 31, 4, 2, 123, 45, 2, 3, 4, 5, 7];
let sortedArray = mergeSort(array);

병합정렬은 배열을 하위배열로 나눈다음 배열을 두개 씩 비교하면서 정렬하고 다시 병합해나가는 정렬입니다.

아직 재귀를 어려워해서 이해하는데에 조금 애를 먹었습니다 ;;