공부 내용

중간고사 대비를 위해 sorting 알고리즘에 대해 공부하고 정리하는 시간을 가졌습니다.

💡 정렬 알고리즘

• 기본적인 정렬 알고리즘
  • 시간 복잡도: Θ(n²)
  • Selection Sort, Insertion Sort, Bubble Sort
• 고급 정렬 알고리즘
  • 시간 복잡도: Θ(nlogn)
  • Merge Sort, Quicksort, Heapsort
• 특수 정렬 알고리즘
  • 특수한 경우에 시간복잡도 Θ(n) 쩐다!!
  • Radix Sort, Counting Sort

💡 sorting 알고리즘의 메모리에 따른 구분

• In-place: 추가 메모리를 사용하지 않음
  • ex) basic 3개, quick sort, heap sort
• Out-of-place: 추가 메모리 공간 사용
  • ex) merge sort, counting sort, radix sort

🫧 Bubble Sort

• 왕기본, 최댓값 맨 뒤로 보내기 권법
• 인접한 거 비교해서 맨 뒤로 보내기 반복

def bubblesort(arr):
  n=len(arr)
  for i in range(n,1,-1):
    # or range(n-1,0,-1), range(i)
    for j in range(i-1):
      if arr[j] >arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
  return arr

⛏️ Selection Sort