알고리즘

1. 재귀 알고리즘

사전적 정의: 어떠한 것을 정의할 때 자기 자신을 참조하는 것

재귀 함수는 탈출 조건(기저 조건)이 반드시 필요하다.
1. 없는 경우 무한 루프에 빠지개 된다.

const myFunction = (number) =>{
  if(number > 10) return; // 기저 조건
  console.log(number)
  myFunction(number + 1)
}

myFunction(1);

하향식 계산 방식과 상향식 계산방식이 있는데 하향식 계산 방식은 오직 재귀함수만 구현 가능하다.

2. 콜스택

함수를 호출하면 그 함수는 콜스택에 올라가게 된다.
스택 자료구조를 잘 표현한 예시

3. 정렬

1. 버블 정렬

앞에 있는 숫자와 옆에 숫자를 비겨해서 자리를 바꾸는 알고리즘
O(n제곱)
장점 : 이해와 구현이 간단 한다
단점 : 성능이 좋지 않다

2. 선택정렬

정렬되지 않은 배열의 가장 작은 값을 첫 번째 원소로 가져오는 알고리즘
첫 번째 원소를 시작으로 마지막 원소까지 비교후 가장 작은 값을 원소로 가져온다.
버블정렬과 같이 O(n제곱)
장점 : 이해와 구현이 간단 한다
단점 : 성능이 좋지 않다

3. 삽입정렬

배열을 정렬된 영역과 정렬되지 않은 영역으로 나누어 정렬된 부분에 삽입 하는 알고리즘
성능 : O(n제곱)
장점 : 이해와 구현이 간단 한다
단점 : 성능이 좋지 않다

4. 병합정렬

재귀로 정렬하는 알고리즘

성능 : n개의 데이터를 n번 비교 O(nlogn)의 성능을 가진다.
장점 : 성능이 좋다
단점 : 이해 및 구현이 어렵다

5. 퀵정렬

분할 정복 알고리즘 재귀를 사용한다.
성능 :
1. Θ(nlogn)의 성능을 가진다
2. 피벗이 중간이 아닌 한쪽으로 치우쳐진 경우 O(n제곱)의 성능을 가질 수 있다.
성능은 병합 정렬이 좋으나 퀵정렬이 더 적은 비요과 더 적은 메모리 공간을 차지한다.

leftStartIndex : 피벗보다 큰값을 만나면 멈춘다.
rightStartIndex : 피벗보다 작은 값을 만나면 멈춘다.
두가지 조건이 만족하면 leftStartIndex 와 rightStartIndex의 값의 위치를 바꾼다.

rigthStartIndex와 leftStartIndex의 위치가 서로 지나치면
피벗과 rightStartIndex의 위치 변경

두 개의 영역으로 나누어 작업을 다시 진행