[Algorithm] 재귀와 정렬

in Algorithm

Elice Algorithm Code Challenge - Day 4 (재귀와 정렬)

목차

  1. 재귀
  2. 정렬

재귀

  • 재귀 : 자신을 정의할 때, 자기 자신을 참조하는 것
  • 재귀 함수 : 함수 내부에서 자기 자신을 호출하는 함수
  • 주의할 점
    • 무한 루프에 빠지지 않도록 종료 조건을 잘 설정
      • 종료 조건을 기저 사례 (base case)라고도 함
    • 함수의 파라미터 및 인자 설정에 유의

정렬

  • 정렬의 종류
    • 삽입 정렬 (Insertion Sort)
      • 최악 O(n^2)
    • 버블 정렬 (Bubble Sort)
      • 최악 O(n^2)
    • 합병 정렬 (Merge Sort)
      • 최악 O(nlogn)
    • 퀵 정렬 (Quick Sort)
      • 최악 O(n^2)
      • 평균 O(nlogn)
      • 설명
        • 배열의 요소들 중에서 피벗(Pivot)을 정하여, 피벗의 앞에는 피벗보다 작은 원소들이 오고, 피벗 뒤에는 피벗보다 큰 값이 오도록 배열을 둘로 나눔
        • 분할된 두 개의 배열의 크기가 0이나 1이 될 때까지, 분할된 두 배열에 대해 재귀적으로 이 과정을 반복
        • 재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소가 최종적인 위치에 있게 되므로, 종료됨이 보장
    • 힙 정렬 (Heap Sort)
      • 최악 O(nlogn)
  • 특정 정렬이 빠르다고 항상 좋은 것은 아님
    • 데이터의 특성, 크기에 따라 적절한 방법 사용해야 함
  • 언어들의 라이브러리 내장 sort 구현
    • C++
      • 인트로 정렬 (Intro Sort)
        • 퀵 정렬 + 힙 정렬 + 삽입 정렬
    • Python
      • 팀 정렬 (Tim Sort)
        • 합병 정렬 + 삽입 정렬
    • Java
      • Java7 이전에는 병합 정렬, 이후에는 팀 정렬
  • 코테에선 왠만하면 내장 sort함수를 사용