선형 검색, 이진 검색, 버블 정렬

기존 블로그에 작성한 내용을 velog로 이전한 글입니다

연습문제

1. 선형 검색

선형 검색을 통해 주어진 배열(array)에 주어진 값(target)이 요소로 존재하는지 확인하여 존재하는 경우 해당 인덱스를 반환하고 존재하지 않는 경우 -1을 반환하는 함수를 구현하라. 단, 어떠한 빌트인 함수도 사용하지 않고 for 문을 사용하여 구현하여야 한다.

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}

console.log(linearSearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(linearSearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(linearSearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(linearSearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(linearSearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 7)); // -1

2. 이진 검색

이진 검색을 통해 주어진 배열(array)에 주어진 값(target)이 요소로 존재하는지 확인하여 존재하는 경우 해당 인덱스를 반환하고 존재하지 않는 경우 -1을 반환하는 함수를 구현하라. 단, 아래의 빌트인 함수 이외에는 어떤 빌트인 함수도 사용하지 않아야 하며, while 문을 사용하여 구현하여야 한다.

1차

function binarySearch(array, target) {
  let midIndex = Math.floor(array.length / 2);
  let maxIndex = array.length - 1;
  let minIndex = 0;

  while (maxIndex !== midIndex) {
    if (array[midIndex] > target) {
      maxIndex = --midIndex;
    } else if (array[midIndex] < target) {
      minIndex = ++midIndex;
    } else {
      return midIndex;
    }
    midIndex = Math.floor((maxIndex + minIndex) / 2);
  }

  return array[midIndex] === target ? midIndex : -1;
}

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

문제점:

• while문이 끝나도 찾는 값이 마지막에 있거나 없는 경우를 한번 더 가려야함
• 변수 이름이 전부 m으로 시작해서 가독성이 떨어짐
• while문 첫줄에 Math.floor를 쓰면 while문 안에만 Math.floor 사용 가능

2차

function binarySearch(array, target) {
  let startIndex = 0;
  let endIndex = array.length - 1;
  let midIndex;

  while (startIndex <= endIndex) {
    midIndex = Math.floor((startIndex + endIndex) / 2);
    if (array[midIndex] < target) {
      startIndex = ++midIndex;
    } else if (array[midIndex] > target) {
      endIndex = --midIndex;
    } else {
      return midIndex;
    }
  }
  return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(binarySearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // -1

개선점:

• while문의 조건식 개선
• 변수 이름 변경
• Math.floor 중복 사용 개선

3. 버블 정렬

버블 정렬을 통해 주어진 배열(array)을 정렬하는 함수를 구현하라. 단, 어떠한 빌트인 함수도 사용하지 않고 for 문을 사용하여 구현하여야 한다.

1차

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

console.log(bubbleSort([2, 4, 5, 1, 3])); // [1, 2, 3, 4, 5]
console.log(bubbleSort([5, 2, 1, 3, 4, 6])); // [1, 2, 3, 4, 5, 6]
console.log(bubbleSort([3, 1, 0, -1, 4, 2])); // [-1, 0, 1, 2, 3, 4]

문제점:

• while문을 한번 돌 때마다 배열의 최대값 순으로 오른쪽 정렬이 되어가는데 루프문을 쓸 데 없이 많이 돈다.

2차

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

console.log(bubbleSort([2, 4, 5, 1, 3])); // [1, 2, 3, 4, 5]
console.log(bubbleSort([5, 2, 1, 3, 4, 6])); // [1, 2, 3, 4, 5, 6]
console.log(bubbleSort([3, 1, 0, 11, 4, 2, 9, -1])); // [-1, 0, 1, 2, 3, 4]

개선점:

• 루프 반복마다 최대값 순으로 하나씩 정렬이 완성되므로 -i를 추가하여 루프 회수를 줄임