TIL 23일차_정렬, 재귀

정렬과 재귀

---

정렬

정렬은 배열에만 적용되는 개념이라고 할 수 있다.
그 이유는, 배열과 객체의 가장 큰 차이인 순서때문이다.
배열에서만 순서라는 값이 적용되므로
정렬을 한다는 의미는 배열을 사용한다는 의미와 같다.

array.sort

var items = [
  { name: 'Edward', value: 21 },
  { name: 'Sharpe', value: 37 },
  { name: 'And', value: 45 },
  { name: 'The', value: -12 },
  { name: 'Magnetic', value: 13 },
  { name: 'Zeros', value: 37 }
];

// value 기준으로 정렬
items.sort(function (a, b) {
  if (a.value > b.value) {
    return 1;
  }
  if (a.value < b.value) {
    return -1;
  }
  // a must be equal to b
  return 0;
});

sort의 콜백함수의 매개변수로 a,b가 들어가는데 이 값은
a,b를 줄꺼니까 순서를 정해줘! 라는 의미로 생각하면 쉽다.

정렬하고자하는 기준에 a,b를 넣고 (위에서는 a.value와 b.value)
a를 넣은 값이 크면 1을 리턴 (내림차순으로 정렬한다면 -1을 리턴)한다. b는 반대로.

뭐가클때 1인지-1인지 헷갈리는데
a를기준으로 생각하면 그나마 편하다.
오름차순 일때는 a<b일때, a를 먼저정렬해야하니까 -1과1중 작은값인 -1을 넣자! 이런식으로 :)

• sort는 원본을 변형시키는 mutable method이다.

재귀적으로 생각하기

재귀함수 : 자기자신을 호출하는 함수

1. 입력값과 출력값을 생각한다.

2. 문제를 어떻게 쪼갤지 고민한다.

입력값을 기준으로 순서와 크기를 생각하며, 쪼갠다.
구분된 문제들을 푸는 방식이 같다면 제대로 구분한 것이다.

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)이라고 부른다. 재귀의 기초는 나중에 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게된다.

4. 복잡한 문제 해결하기

맨 앞의 요소를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이자), 나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더한다.
배열이 있을 때 head와 나머지 부분(tail)을 구분하는 방법만 안다면, 재귀함수를 작성할 수 있다.

5. 코드구현하기

재귀함수 템플릿
function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

ex)

arr 요소 다 더하기
function arrSum(arr) {
// 재귀의 기초 (base case)
// 문제를 더 이상 쪼갤 수 없을 경우
if (arr의 길이가 0인 경우) {
    return 0;
}
// recursive Case
// 그렇지 않은 경우
// head: 배열의 첫 요소
// tail: 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}

Today's ?!

1. shortcut circuit

디폴트값을 지정할 때 주로 쓴다.
order = order ||1
= order값이 주어졌으면(true이면) order값을 쓰고
order값이 없으면(false이면) 1을 쓴다.

• OR연산자, AND연산자를 쓸 때 생각할 점

비용이 높은(무거운)코드를 연산자에 넣을 때 생각해서 넣자.
OR연산자를 사용할 땐, true를 리턴할 가능성이 높은 코드를 첫번째 조건으로 작성하고,
AND연산자를 사용할 땐, false를 첫번째 조건으로 작성해야 메모리의 낭비가 줄어든다.
최대한 적은 조건만 확인하고 넘어가도록!

2. 배열 내장 함수를 쓰는 이유

배열 내장 함수 5대장
forEach, filter, map, reduce, sort

배열내장함수 모두 for loope로 구현가능하다.
그러나 이들을 사용함으로써 코드의 가독성과 표현력(expression)을 향상시킨다.