50

참고 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

function bubble(arr) {
  let result = arr.slice(); //원본배열 복사

  for (let i = 0; i < result.length - 1; i++) {
    for (let j =0; j<result.length - i; j++) {
      if (result[j] > result[j + 1]) {
         let temp = result[j] //자리를 바꾸는 코드
		 result[j] = result[j+1]
         result[j+1] = temp;
      }
    }   //인덱스0을 비교하고 맨 끝에 가장큰 숫자가 놓이게되면 다음 인덱스1번 돌릴땐 마지막 숫자는 안해도 되니까 length-i 해주는거..
  }
  return result;
}

const items = prompt('입력해주세요.').split(' ').map((n) => {
  return parseInt(n, 10);
});

console.log(bubble(items));

51

merge sort

일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.

• 분할 정복(divide and conquer) 방법
  문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
  분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
  
  
• 과정 설명
  리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
  정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

다음 코드의 빈칸을 채워 병합정렬을 완성해 봅시다.

function mergeSort(arr){

  if (arr.length <= 1){ //인자 두개인 배열이면 그대로 반환해라
    return arr;  //ending조건
  }

  const mid = Math.floor(arr.length / 2); //반으로 자르는 코드
  const left = arr.slice(0, mid); // 좌측 배열
  const right = arr.slice(mid); //우측 배열

  return merge(mergeSort(left), mergeSort(right)); //재귀함수, 
  //재귀로 인자 두개이하의 배열이 나올때까지 쪼개짐.. 
  //다 끝나야 merge 가 실행됨.
}

function merge(left, right){
  let result = [];

  while (left.length && right.length){ // 들어오는 두 배열 안에 계속 값이 있으면 실행한다.
    if (left[0] < right[0]){ 
      result.push(left.shift());//shift 메소드는 맨 첫번째 값을 삭제하며 반환한다.
    } else {
      result.push(right.shift());
    }
  }
  //한쪽이 끝나서 값이 없을경우
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }

  return result;
}


const array = prompt('배열을 입력하세요').split(' ').map(n => parseInt(n, 10));


console.log(mergeSort(array));

다른분 풀이 : https://jun-choi-4928.medium.com/javascript%EB%A1%9C-merge-sort-%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%AC-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-c13c3eee6570