2021.8.14 TIL(선택 정렬, 버블 정렬)

목차

교육 과정 설계

선택 정렬

버블 정렬

 

---

 

교육 과정 설계

1년 교육 과정과 필수 과정이 주어졌을 때 필수 과정은 반드시 그 순서대로 진행되어야 하고, 생략해서도 안된다. 예를 들어 'ABC' 필수 과목과 'ADBEC' 는 A를 수료한 뒤에 B, C를 순서로 이수했기 때문에 올바른 설계다. 반면, 'ADCEB'는 필수 과목 순으로 이수하지 않는 설계로 틀렸다.

 

function edu(obl, plan) {
  let answer;
  // code here
  return answer;
}

 

 

답) 필수 과목을 순서대로 돌아가며, plan 에서의 인덱스를 체크한다

 

function edu(obl, plan) {
  let answer = true;
  let cnt = -1;
  for(let el of obl) {
    let idx = plan.indexOf(el);
    idx > cnt ? cnt = idx : answer = false;
  }
  return answer;
}

 

 

답2) plan를 배열화 하고, 필수 과목을 필더링 하고, 비교한다

 

function edu(obl, plan) {
  return obl === plan.split('').filter(a => obl.includes(a)).join('')
}

 

 

선택 정렬

선택 정렬(selection sort)는 주어진 리스트 들을 순서대로 돌아가며, 최소값을 찾고 위치를 변경한다. 보통 주어지는 배열을 이용해서 정렬해야 한다. 추가로 배열이나 객체를 선언할 수 없다는 조건이 덧붙여진다. (공간 복잡도를 최소로 하기 위해, 자바스크립트에선 보통 고려되지 않지만)

 

• [15, 3, 2, 8, 11]
• [2, 3, 15, 8, 11]
• [2, 3, 15, 8, 11]
• [2, 3, 8, 15, 11]
• [2, 3, 8, 11, 15]

 

function selection(num) {
  // code here
  return num;
}

 

 

답) Math.min()매소드를 이용할 수 있을 때

 

function selection(num) {
  for(let i = 0; i < num.length; i++) {
    let sliced = num.slice(i, num.length);
    let min = Math.min(...sliced);
    let idx = num.indexOf(min);
    [num[i], num[idx]] = [num[idx], num[i]]
  }
}

 

 

답2) Math.min()사용할 수 없을 때

 

function selection(num) {
  for(let i = 0; i < num.length; i++) {
    let idx = i;
    for(let j = i + 1; j < num.length; j++) {
      num[j] < num[idx] ? idx = j : idx;
    }
    [num[idx], num[i]] = [num[i], num[idx]];
  }
  return num;
}

 

 

버블 정렬

버블 정렬은 주어진 배열을 순차적으로 돌면서 양옆의 원소들의 값을 비교하여 자리 정렬을 한다. 모든 배열이 더 이상 바꿀 필요가 없을 때까지 반복한다. 선택 정렬과 마찬가지로 추가로 빈배열이나 빈 객체(object)를 선언하는 것은 허용되지 않는다. 원 배열을 조작하여 정렬된 원 배열을 리턴한다. 특이한 점은 한 번 싹 배열을 훑고 가면, 가장 큰 수가 배열의 맨 뒤로 정렬이 완료된다는 점이다. 따라서 다음 번 배열을 싹 훑을 때는, 마지막 배열을 제외하고 배열을 돌면된다.

 

• [15, 3, 2, 8, 11]
• [3, 15, 2, 8, 11]
• [3, 2, 15, 8, 11]
• [3, 2, 8, 15, 11]
• [3, 2, 8, 11, 15] // 한 바퀴를 돈 상태 (제일 큰 수는 제일 뒤로 감)
• [2, 3, 8, 11, 15]

 

function bubble(num) {
  // code here
  return num;
}

 

 

답) 한 번도 교체 안할 때까지 앞뒤로 정렬해줌

 

function bubble(num) {
  let cnt;
  while(cnt !== 0){
    for(let i = 0; i < num.length - 1; i++) {
      if(num[i] > num[i+1]) {
        [num[i], num[i+1]] = [num[i+1], num[i]];
      }
      if(i === num.length - 2) cnt --;
    }
  }
  return num;
}

 

 

답2) 버블 소트가 한 번 돌고 나면, 제일 큰 수 순으로 뒤로 가게 된다는 점을 이용(정석)

 

function bubble(num) {
  for(let i = 0; i < num.length - 1; i++) {
    for(let j = 0; j < num.length - 1 - i; j++) {
      if(num[j] > num[j+1]) {
        [num[j], num[j+1]] = [num[j+1], num[j]];
      }
    }
  }
  return num;
}