좋은 알고리즘

• 정확성, 효율성

재귀에서 중요한거 세가지

• 베이스 케이스, 예측 케이스, 그리고 자기자신 함수 호출

분할 정복

• 복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법
• 특징: 병렬적으로 문제를 해결할 수 있음
  but 문제 해결 함수가 재귀적으로 호출될 수 있으므로 메모리가 추가적으로 사용될 수 있음
• 재귀 호출은 같은 함수코드를 재호출(같은 함수코드 사용)
• 분할정복은 비슷한 작업을 재진행(같은 함수코드는 아닐 수 있음)

퀵 정렬, 병합 정렬

• 퀵 정렬은 불안전 정렬이고 병합정렬은 안정 정렬이다

퀵 정렬이 사용되는 이유

• 피벗이라는 별도의 노드를 지정해두고 재귀적으로 수행을 하기 때문에 통상적으로 병합정렬보다 더 빠르다
• 처음과 끝을 계속해서 탐색해서 퀵소트에 비해 느림

병합 정렬이 활용되는 이유

• 퀵 정렬보다 빠르지는 않지만, 안정 정렬이기 때문에 데이터가 중복되었더라도 영향을 덜 받기 때문
• 퀵 정렬은 성능이 우수함에도 성능 편차가 크고, 피벗(노드) 설정 등의 다루기 어려운 점이 존재하기 때문에
  실무에서는 활용되기 어려움

퀵정렬

• 퀵정렬은 불안정 정렬의 대표적인 경우로서, 노드의 값이 중복되는 경우에는 계속해서 swap(교환)을 시도함
• 퀵정렬은 최악의 경우에 첫번째 노드를 피벗으로 설정하고 불균형하게 분할정복을 시도하여 성능이 안 좋아짐
  • 속도는 알고리즘을 처리하고 결과를 도출하는 속도(주로 소프트웨어에 영향을 주고 받음)
  • 성능은 메모리에 영향을 주는 정도(주로 하드웨어에 영향을 주고 받음)

병합정렬

• 접근 방식 1. 분할정복 방법의 분할 구성 요소를 수행
  • 초기 리스트를 더 작은 구성요소로 나눔
  • 초기 리스트 분할은 분리된 각 구성 요소를 더 이상 분할할 수 없는 경우에 중지
• 접근 방식 2. 전달받은 리스트 내의 요소를 지정된 순서로 정렬하는 작업