리스트에 저장된 값들을 크기 순서에 따라 재배열하는 문제

→ 되도록 비교 횟수와 자리바꿈 횟수를 최소로 하는 것이 목표

정렬 알고리즘의 성질 2가지

Stable vs Unstable

• 크기가 같은 숫자인 경우, 원래 입력 순서를 정렬 후에도 유지 ⇒ Stable

  

  출처 : https://en.wikipedia.org/wiki/Sorting_algorithm

In-place vs Not-in-place

• 상수 개의 추가 메모리($O(1)$)만 사용한 정렬 ⇒ In-place

기본 정렬 알고리즘

→ $(n-1)$번의 round마다 숫자 1개씩 sort

→ 느리지만 간단한 알고리즘

• Insertion Sort (삽입 정렬)

   def insertion_sort(arr, n):
      for i in range(1, n):
          j = i - 1
          while arr[j] > arr[j + 1] and j >= 0:
              arr[j], arr[j + 1] = arr[j + 1], arr[j]
              j -= 1
  

  ⇒ $\frac{n(n-1)} 2$번 비교, $\frac{n(n-1)} 2$번 교환 ⇒ $O(n^2)$

• Selection sort (선택 정렬)

  def selection_sort(arr, n):
      for i in range(n):
          x = i
          for j in range(i + 1, n):   # arr[i + 1] 부터 arr[n - 1] 중 최솟값 인덱스 찾기
              if arr[x] > arr[j]:
                  x = j
          arr[i], arr[x] = arr[x], arr[i]     # swap
  

  ⇒ $\frac {n(n-1)} 2$번 비교, $(n-1)$번 교환 ⇒ $O(n^2)$

• Bubble sort (버블 정렬)

  def bubble_sort(arr, n):
      for i in range(n):
          for j in range(i + 1, n):
              if arr[i] > arr[j]:
                  arr[i], arr[j] = arr[j], arr[i]
  

  ⇒ $\frac{n(n-1)} 2$번 비교, $\frac{n(n-1)} 2$번 교환 ⇒ $O(n^2)$

  정렬 최악의 수행시간 - stable - inplace

Insertion $O(n^2)$ stable inplace

Selection $O(n^2)$ Unstable inplace

Bubble $O(n^2)$ stable inplace

Quick Sort (퀵 정렬)