정렬

1. 재귀 함수 - 피보나치 수열

def fib(arr, idx, len):
  if idx == len:
    return
  arr.append(arr[idx-1] + arr[idx])
  fib(arr,idx+1, len)
#arr=[2,4], fib(arr,1,4)
#[2, 4, 6, 10, 16]

2. Big-O

시간 복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수
공간 복잡도 : 알고리즘이 실행될 때, 사용하는 메모리의 양

3. 정렬 알고리즘

— Merge sort $O(n log n)$
대표적인 stable한 정렬알고리즘, 분할 정복 방식
리스트를 둘로 분할 -> 둘로 분할 -> 둘로 분할 로 각 요소 비교 후 합치는 방식
— Insertion sort $O(n ^{2} )$
간단하지만 입력배열의 크기가 작을 때는 속도가 빠름, 주로 다른 정렬알고리즘과 함께 사용
— Heap sort $O(n log n)$
“부모의 값이 자식의 값보다 언제나 크다” 최소 힙의 경우 반대
— Bubble sort $O(n ^{2})$
인접한 두 개의 요소를 비교하여 위치 교환, 일반적으로 잘 사용하지 않음
— Quick sort $O(n log n)$
unstable한 정렬 알고리즘, 분할 정복 알고리즘

4. Quick sort

🎈 효율적이다
입력배열 외에 추가적인 공간을 사용하지 않고 스택 프레임을 사용
🎈 시간 복잡도가 빠르고, 공간 복잡도가 작다
🎈 분할 정복 알고리즘
But, unstable : 입력 배열의 순서에 따라 결과가 달라질 수 있음
안정성이 필요하지 않은 경우에는 다른 알고리즘보다 효율적

def qsort (a,left,right):
  pl = left
  pr = right
  x=a[(left+right)//2] #pivot
  
  while pl <=pr:
    while a[pl] < x: pl+=1
    while a[pr] > x: pr-=1
    
    if pl <= pr:
      a[pl],a[pr] = a[pr], a[pl]
      pl+=1
      pr-=1
    if left<pr:
      qsort(a,left,pr)
      
    if pl<right:
      qsort(a,pl,right)