algo_lec19

 

Why Sorting and Searching?

• Practical use: 많은 프로그램에서 실행 시간의 상당 부분이 정렬 및 탐색에 소비됨.
• 다양한 접근법: 동일 문제에 대해 다양한 알고리즘 존재.
• 좋은 하한 존재: 최악/평균 시간 복잡도에 대한 이론적 하한 존재.

Sorting Algorithms 분류

1. Key Comparison 기반 정렬
   • Simple algoritms: Insertion Sort, Selection Sort, Bubble Sort
     • 시간복잡도: 평균 및 최악 모두 Θ(n²)
   • Advanced algorithms: Quicksort, Mergesort, Heapsort
     • Quicksort:  W(n) = Θ(n²), A(n) = Θ(n log n)
     • Mergesort, Heapsort: A(n) = W(n) = Θ(n log n)
   • Shellsort: Insertion sort 일반화
2. Key Distribution 기반 정렬
   • Bucket Sort
   • Radix Sort

Review: Selection Sort

• 왼쪽은 정렬된 리스트, 오른쪽은 미정렬 리스트.
• 오른쪽에서 최소값을 찾아 왼쪽 끝에 삽입.
• 동일한 최소값이 여러 개면 앞쪽에 있는 값을 선택.

def selectionSort(array, size):
    for ind in range(size):
        min_index = ind
        for j in range(ind + 1, size):
            if array[j] < array[min_index]:
                min_index = j
        array[ind], array[min_index] = array[min_index], array[ind]

• Time complexity: O(n²), Auxiliary space: O(1)
• Not sensitive to the input type. 입력 상태(역순 등)에 민감하지 않음.

Review: Insertion Sort

• 오른쪽에서 하나씩 왼쪽에 정렬된 리스트에 알맞은 위치에 삽입.
• 이미 정렬된 입력에 대해 빠르고, 역순일 경우 느림.

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

• Time complexity: If arr is reversed, 평균 O(n²) / If arr is already sorted, 최선 O(n)
• Auxiliary space: O(1)

Review: Bubble Sort

• Keep wapping adjacent entries until the list is sorted.
• 인접한 두 원소를 비교하여 큰 값을 오른쪽으로 보내는 방식 반복.

def bubbleSort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                swapped = True
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if not swapped:
            return

• Time complexity: O(n²) (Comparison count)
• Auxiliary space: O(1)

---

Sorting Algorithm Complexity (이론적 하한)

• Insertion sort, Selection sort, Bubble sort는 모두 in-place sort → require O(1) extra space
• worst-case and average-case time complexity = Θ(n²).
• 이러한 정렬 알고리즘은 매우 큰 입력에 대해서는 비효율적.
• Θ(n²) 이상의 개선은 불가능하다는 이론적 근거가 있음 (단, 키 비교 기반 알고리즘에 한정).
• 로컬 이동(local moves) 만 사용하는 정렬 알고리즘은 모두 insertion sort 수준의 작업량 필요.
  • 예: 한 번의 비교로 인접 원소만 교환.

---

• 순열 기반 설명
  • 주어진 n개의 키를 x₁, x₂, ..., xₙ 이라 할 때, 정렬 상태를 나타내는 순열 π가 존재함.
    • π(i): 키 xᵢ가 정렬 후 들어가야 할 정위치(index) "the correct position of xᵢ"
  • For example,
    • 입력: (2, 4, 1, 5, 3)
    • 정렬 결과: (1, 2, 3, 4, 5)
    • 따라서 π(1)=2, π(2)=4, π(3)=1, π(4)=5, π(5)=3
  Inversion(역순쌍)의 정의
  • (π(i), π(j))가 inversion이면 i < j 이고 π(i) > π(j)
  • 즉, 정렬 순서에 어긋나는 쌍을 의미함.
  • For example,
    • π = (2, 4, 1, 5, 3) → π(1)=2, π(2)=4, π(3)=1, π(4)=5, π(5)=3
    • inversion 쌍들: (2,1), (4,1), (4,3), (5,3)

---

• 어떤 정렬 알고리즘이 한 번의 비교로 최대 한 개의 inversion만 제거할 수 있다면,
  해당 정렬 알고리즘은 최소한 입력 내의 inversion 수만큼의 비교가 필요하다.

The maximum # of inversions:

• 입력이 완전히 역순일 경우 (n, n-1, ..., 2, 1),
  • inversion 쌍의 개수는 n(n-1) / 2.​
  • 즉, 가능한 inversion의 최대 개수. 

결론:

• 비교 기반 정렬에서, worst case의 경우에는 최소 n(n−1) / 2 = Θ(n^2)번의 비교가 필요.

---

Revisit Quick Sort

• 첫 원소를 pivot으로 선택 시 최악의 경우 Θ(n²)
• Randomized Quick Sort:
  • pivot을 무작위로 선택 → 성능 향상 및 편향 피함.
  • 단순하면서도 많은 경우에 효과적.

Such randomness can reduce the chances to pick MIN and MAX as pivot

Any other way not to pick a pivot at MIN and MAX?
MIN이나 MAX를 피벗으로 고르지 않는 다른 방법은 없을까?

---

Quick Sort with Stack

• 재귀호출을 스택으로 구현하여 스택 크기를 줄일 수 있음.
• 개선 방법:
  • 항상 더 작은 파티션부터 먼저 정렬.
  • 큰 쪽은 나중에 스택에 push → 스택 크기 O(log n)

재귀 호출 흐름 (Call Stack 순서)

1. quickSort(arr, 0, 7) 호출
- 피벗: 5 → 결과: [1, 3, 2, 4, 5, 6, 8, 7]
- 이후 왼쪽 (low=0, high=3) 과 오른쪽 (low=5, high=7)로 나눠짐

2. 왼쪽: quickSort(arr, 0, 3)
- 피벗: 4 → 결과: [1, 2, 3, 4]

3. 그 왼쪽: quickSort(arr, 0, 2)
- 피벗: 2 → 결과: [1, 2, 3]
- 이때 왼쪽(0,0)과 오른쪽(2,2)은 이미 정렬 완료

∴ 왼쪽 분할 종료 → 이제 오른쪽 호출로 이동

4. 오른쪽: quickSort(arr, 5, 7)
- 배열: [6, 8, 7]
- 피벗: 7 → 정렬 후: [6, 7, 8]

 

Python Code:

def quickSort(arr, low, high):
    while (low < high):
    #pi is pivot index and arr[p] is now at right place,
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)       # 피벗 왼쪽 정렬
        print("quickSort call:", pi, low, pi - 1, arr)
        low = pi + 1                      # 반복문으로 오른쪽 정렬

def partition(array, low, high):
	#Chosse the rightmost element as pivot
    pivot = array[high]
    i = low - 1
    #compare each element with pivot
    for j in range(low, high):
        if array[j] <= pivot:
        #If element smaller than pivot, swap it with th greater element i
            i += 1
            #Swapping element at i with element at j
            array[i], array[j] = array[j], array[i]
    #Swap the pivot element with the greater element i
    array[i + 1], array[high] = array[high], array[i + 1]
    #Return the position from where partition is done
    return i + 1

---

 

Quick Sort with Stack (Better Approach)

문제: 일반 Quick Sort의 재귀 호출

• 재귀적으로 좌우 서브배열을 모두 호출하면,
  • 최악의 경우 (예: 이미 정렬된 배열에서 항상 pivot이 최소값 또는 최대값으로 선택되는 경우)
  • stack size: O(n) 까지 증가할 수 있음 → Stack Overflow 가능

개선된 논리:

한쪽(더 큰 쪽) 서브배열은 재귀 호출하지 않고 반복문으로 처리.
작은 쪽만 재귀 호출하여 스택 깊이 감소

if (there is X such that length(X) < n/2):
    quickSort(X)  # 작은 쪽 먼저 재귀 호출
else:
    partition X into X’ and X’’

• 항상 작은 부분 배열을 재귀 호출하고,
• 큰 부분 배열은 반복문(loop)으로 처리.
• 이를 통해 스택에 push되는 호출 수를 O(log n)으로 줄일 수 있음.

 
스택 크기 감소 효과

• 최악의 경우에도 스택에 최대 O(log n) 개의 호출만 쌓이게 되어
  → 메모리 효율 개선
• 시간 복잡도는 그대로 O(n log n) (평균), O(n²) (최악)이지만,
• stack size는 O(n) → O(log n) 으로 줄어듦.