bubble sort

• 인접한 두 요소를 검사하여 정렬하는 가장 간단한 정렬 알고리즘

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

• 시간복잡도는 언제나 O($n^{2}$)

insertion sort

• 각 반복에서 하나의 요소를 취하여, 그 요소가 올바른 위치에 삽입될 때까지 이미 정렬된 배열 부분과 비교하여 재배치

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 현재 삽입될 요소
        j = i-1
        # 정렬된 부분과 key를 비교하여, key가 적절한 위치에 삽입될 때까지
        # 정렬된 부분의 요소들을 한 칸씩 뒤로 이동
        while j >=0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        # 적절한 위치를 찾았다면 key를 삽입
        arr[j+1] = key
    return arr

• 최선의 경우 시간복잡도 O(n)
  • 이미 정렬된 배열에서는 각 요소가 정확히 한 번씩만 비교됨
• 최악의 경우 시간복잡도 O($n^2$)
  • 대부분의 경우나 배열이 역순으로 정렬되어 있는 경우, 첫 번째 요소를 제외한 모든 요소는 자신보다 앞에 있는 모든 요소와 비교됨
  • 예를 들어, 두 번째 요소는 최대 1번, 세 번째 요소는 최대 2번, ..., n번째 요소는 최대 n−1번 비교 => 등차수열의 합 공식에 따라 $\frac{n(n-1)}{2}$ => 빅오표기법에서는 가장 높은 차수의 항만을 고려하며, 계수는 무시함 (같은 $n^2$로 표시되더라도 bubble sort보다는 빠름)

merge sort

• 리스트를 반으로 나누어 각각을 재귀적으로 정렬한 후, 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 병합

def merge_sort(arr):
	# 분할
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

		# 정복
        merge_sort(L)
        merge_sort(R)

		# 병합
        i = j = k = 0

		# L과 R의 요소를 비교하여 정렬
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

		# L 또는 R에 남아있는 요소를 arr에 추가
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    return arr

• 시간복잡도는 언제나 O(nlogn)
  • 병합과정은 각 요소를 한 번씩만 처리하기 때문에 O(n)
  • 분할과정에서 로그 수만큼의 단계가 생성되므로 O(logn)
  • 병합이 여러 분할 단계에서 반복되므로 전체 시간복잡도는 O(nlogn)

quick sort

• 배열의 중간을 pivot이라고 정함
• 피벗보다 작은 요소들은 피벗의 왼쪽, 큰 요소들은 오른쪽으로 이동
• 왼쪽과 오른쪽 리스트를 동일한 방식으로 재귀적으로 정렬

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

• 최선의 경우 시간복잡도 O(nlogn)
  • 피벗이 매번 정확히 배열을 두 동등한 부분으로 나눌 때, 즉 매 분할마다 배열이 거의 반으로 나뉘는 경우
  • 로그 레벨의 깊이를 가진 분할 트리를 생성하며, 각 레벨에서 n에 비례하는 작업을 수행
  • 무작위로 선택된 데이터에 대해 퀵 정렬을 수행할 때에도 일반적으로 최선의 경우와 같다
• 최악의 경우 시간복잡도 O($n^2$)
  • 피벗 선택이 매번 최소값이나 최대값으로 이루어져 배열이 한 쪽으로 치우쳐 분할될 때, 즉 한 부분은 n−1 요소를 가지고 다른 한 부분은 0 요소를 가질 때
  • 분할 트리의 깊이가 n이 되며, 각 레벨에서 n에 비례하는 작업을 수행
• 데이터 분할 최적화: 퀵 정렬의 성능을 개선하기 위해, 작은 배열에 대해서는 삽입 정렬과 같은 더 간단한 정렬 방법을 사용하는 하이브리드 접근 방식 적용
• 재귀 깊이 제한: 최악의 경우를 방지하기 위해 재귀 호출의 깊이에 제한을 두거나, 너무 깊어지는 경우 다른 정렬 방법으로 전환