정렬

Counting Sort

개수 정렬!

핵심은!

숫자와 같은 인덱스에 숫자 보관하기

ex) 정렬할 배열에 숫자 2 가 있다면 새로운 배열의 index 2에 +1 을 해준다.
: 한마디로 숫자 2를 싹 찾아서 인덱스 2에 숫자 2의 갯수를 넣어둔다!

const nums = [2,1,2,3,4,5,2,5,6,7];

// 정렬할 배열의 가장 큰 숫자 만큼의 길이 배열을 만들고 모두 0 넣어주기
let arr = [0,0,0,0,0,0,0];

// nums 의 0번째 숫자는 2!
// arr 의 index 2 에 +1 하기
// HINT : arr[Number(nums[0])]++
arr = [0,0,1,0,0,0,0];

// 똑같이
// nums 의 1번째 숫자는 1!
// arr 의 index 1 에 +1 하기
arr = [0,1,1,0,0,0,0];
// 반복!
.
.
.
arr = [0,1,3,1,1,2,1,1];

// 이제 뿌려주기!
// arr index 0은 0개! index 1은 1개, index 2는 3개!
// 0개인 숫자는 뿌려주지 않는다!

const newArr = [1,2,2,2,3,4,5,5,6,7];

Merge Sort

병렬 정렬!

쪼개고 쪼개고 쪼개고 쪼개서 한 개씩 남을때까지 쪼갠 후 비교하면서 다시 합치기!

const nums = [3,2,1,3,6,4,5]

// 쪼개는 함수!
function divide (arr){
  // 배열의 길이가 쪼갤수 없는 1개 이면 그대로 리턴!
  if(arr.length < 2) return arr
  // 배열의 길이를 나누어 배열을 쪼갠다.
  let half = Math.floor(arr.length/2);
  // 절반까지 left, right 로 나누기
  let left = arr.slice(0,half);
  let right = arr.slice(half, arr.length);
  // 합치쳐서 return!
  // 재귀 사용! 쪼갤 수 없을때 까지 쪼개고 다시 합치면서 리턴되어 돌어온다.
  return merge(divide(left),divide(right));
}

// 합치는 함수
function merge(left, right){
  let result = [];
  // left, right 양쪽 배열에 수가 모두 있으면 while 계속 돈다.
  // 즉, left, right 둘 중 하나의 배열이라도 텅 비게 되면 while STOP!
  while(left.length && right.length){
    // 양쪽 배열의 첫번째 수를 비교하여
    if(left[0]<=right[0]){
      // 더 작은 쪽을 꺼내어 result 배열로 넣어준다.
      // 당연히 해당 배열에는 수가 사라지고 result 배열로 옮겨진 것!
      // arr.shift() 배열 맨 앞의 수를 꺼내고 한칸씩 당긴다. 맨 앞수는 return 해줌!
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  // 이후 left, right 배열에 남은 수가 있다면 꺼내어 result에 넣어준다.
  while(left.length) result.push(left.shift());
  while(right.length) result.push(right.shift());
  // left , right 배열에 남은 수없이 result 에 넣어주었으니 result 배열 return!
  return result
}

console.log(divide (nums));
//[1, 2, 3, 3, 4, 5, 6]