알고리즘 정렬(선택, 버블, 삽입)

hodu·2023년 4월 15일

선택정렬 1문제✨

선택 정렬은 맨 앞부터 하나씩 비교해가며
탐색 영역을 지워가는 방법이다.

let num = 6;
let numArray = [13, 5, 11, 7, 23, 15];

let answer = 0;
for (let i = 0; i < numArray.length - 1; i++) {
  // 신경쓸것
  let idx = i;
  for (let j = i + 1; j < numArray.length; j++) {
    if (numArray[idx] > numArray[j]) {
      idx = j;
    }
  }

  [numArray[i], numArray[idx]] = [numArray[idx], numArray[i]]; //기억할 것
}

console.log(numArray);

위 코드는 첫번째 i값에 맞추어서 그 값을 비교하고 그보다 작은 값이 있다면,
idx에 index 값을 넘겨주고
i와 idx의 자리를 바꾸는 방식으로 찾아간다.
지나간 자리는 이미 검증되었으므로, 탐색하지 않아도 된다.

이렇게 하나씩 지우다보면 모든 것이 탐색이 되고 마무리 된다.

let tmp = numArray[i];
numArray[i] = numArray[idx];
numArray[idx] = tmp

과거에는 위와 같은 방법으로 처리하였는데,
배열의 값교환하는 방식이 인상적이었다.

버블정렬✨

버블정렬은 1:1 교환 방식을 통해 배열을 순회하고,
마지막을 제하는 방식이다.
이를 통해 선택정렬보다 더 빠르게 할 수 있지만, 계속해서 할당하기때문에,
메모리 사용량이 증가한다는 단점도 있다.

let num = 6;
let array = [13, 5, 11, 7, 23, 15];

//삽입 정렬도 가능

for (let i = 0; i < num - 1; i++) {
  for (let j = 0; j < num - 1 - i; j++) {
    if (array[j] > array[j + 1]) {
      [array[j], array[j + 1]] = [array[j + 1], array[j]];
    }
  }
}

console.log(array);

위에서도 하나씩 제하는 방법으로 접근하였다.

음수 양수만 정리하기✨

let num = 8;
let array = [1, 2, 3, -3, -2, 5, 6, -6];

for (let i = 0; i < num - 1; i++) {
  for (let j = 0; j < num - 1 - i; j++) {
    if (array[j] > 0 && array[j + 1] < 0) {
      [array[j], array[j + 1]] = [array[j + 1], array[j]];
    }
  }
}
console.log(array);

위에서는 앞에는 양수 뒤에는 음수일 때 자리를 바꿨다.

삽입정렬✨

삽입 정렬은 index 뒤에 있는 값과 index 인 값을 비교하고

그 값이 조건에 맞을 경우 index에 값을 덮는다
그러고 나서 조건이 안맞고 순회가 멈출 경우에
+1을 해서 맞는 자리에 들어가는 방식으로 정렬한다.

let num = 6;
let arr = [11, 7, 5, 6, 10, 9];

for (let i = 0; i < num; i++) {
  let tmp = arr[i],
    j;
  for (j = i - 1; j >= 0; j--) {
    if (tmp < arr[j]) {
      arr[j + 1] = arr[j];
    } else break;
  }
  //마지막에 나갈때  --, ++ 가 적용이 됨
  // 그전까지는for밖을 생각하지 않았지만 for 밖을 나갈떄도 적용이 된다.

  arr[j + 1] = tmp;
}
console.log(arr);

인상적이었던 것은 for문에 j의 스코프를 넗혀서 진행하였더니,

for문이 끝나고 나올때 j--가 한번 더 들어간 상태에서 나오는 것이었다.
궁금해서 for ++도 해봤는데 마찬가지였다.

여지껏 스코프가 for문 안이어서 몰랐던 것이었다.

카카오 캐시 변환 문제✨

let [size, num] = [5, 9];
let arr = [1, 2, 3, 2, 6, 2, 3, 5, 7, 9, 10, 11, 12, 13];

let answer = Array.from({ length: size }, () => 0);

arr.forEach((x) => {
  let idx = -1;
  for (let i = size - 1; i >= 0; i--) {
    if (x === answer[i]) idx = i;
  }

  if (idx === -1) {
    // for (let i = size - 1; i >= 1; i--) {
    //   answer[i] = answer[i - 1];
    // }

    // answer[0] = x;
    answer.unshift(x);
    answer.pop();
  } else {
    // for (let i = idx; i >= 1; i--) {
    //   answer[i] = answer[i - 1];
    // }

    // answer[0] = x;
    answer.splice(idx, 1);
    answer.unshift(x);
  }
});
console.log(answer);