[Seoul National Univ: Data Science] Lecture 3. Sorting

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

 

https://youtu.be/0QK_-ygktyM?si=cWZeennCW0u3XZE8

 

 

1. Insertion Sort

동작 방식

• i = 1부터 시작해서 arr[0..i-1] 구간은 항상 정렬된 상태라고 가정
• key = arr[i]를 들고,
• 왼쪽으로 가면서 key보다 큰 값들을 한 칸씩 뒤로 밀고
• 적절한 위치(j+1)에 key를 꽂는 방식
• 제자리 정렬(in-place)임 → 추가 메모리 O(1)
• 안정 정렬(stable)임 → 같은 값들의 상대 순서 유지됨

Time Complexity

• 최악의 경우: O(N^2) (역순으로 정렬된 상태)
• 최선의 경우: O(n) (이미 정렬된 상태)

code (Python)

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

code (C++)

void insertSort(int arr[], int n) {
	for (int i = 1; i < n; i++) {
    	int key = arr[i];
        int j = i-1;
        
        while (j >= 0 && key < arr[j]) {
        	arr[j+1] = arr[j];
            j--;
        }
        
        arr[j+1] = key;
    }
}

 

 

2. Selection Sort

동작 방식

• 배열에서 매 단계마다 가장 작은 값을 골라 앞으로 보내는 정렬
• i = 0부터 시작해서 arr[0..i-1] 구간은 항상 정렬된 상태라고 가정
• i번째부터 끝까지 arr[i..n-1] 범위에서 가장 작은 원소의 인덱스를 찾는다.
• 찾은 인덱스와 현재 위치의 값을 교환한다.
• i를 1 증가시키고, 위 과정을 i = n-2까지 반복한다.
• 제자리 정렬(in-place)임 → 추가 메모리 O(1)
• 안정 정렬(stable)임 → 같은 값들의 상대 순서 유지됨

Time Complexity

• 최악의 경우: O(N^2) (역순으로 정렬된 상태)
• 최선의 경우: O(n) (이미 정렬된 상태)

code (Python)

def selection_sort(list):
	for i in range(0, len(list)-1):
    	smallest = i
        for j in range(i+1, len(list)):
        	if list[j] < list[smallest]:
            	smallest = j
        list[i], list[smallest] = list[smallest], list[i]

code (C++)

void selectionSort(int arr[], int n) {

	for (int i = 0; i < n-1; i++) {
    	int smallest = i;
        
        for (int j = i+1; j < n; j++) {
        	if (arr[smallest] > arr[j])
        		smallest = j;
        }
        int temp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = temp;
    }
}

 

 

3. Merge Sort

동작 방식

1. 분할 (Divide)

• 배열을 절반으로 계속 나눈다.
• 더 이상 나눌 수 없을 때 (원소 개수 1개가 될 때)까지 재귀 호출.

2. 정복 (Conquer = 재귀 정렬)

• 왼쪽 절반을 정렬
• 오른쪽 절반을 정렬 → “정렬된 두 배열”이 준비되는 구조.

3. 병합 (Merge)

• 정렬된 두 배열(왼쪽, 오른쪽)을 정렬된 하나의 배열로 합친다.
• 왼쪽 배열의 현재 원소와 오른쪽 배열의 현재 원소를 비교해서 더 작은 쪽을 결과 배열에 차례대로 넣어 나감.

안정 정렬(stable)임 → 같은 값들의 상대 순서 유지됨

Time Complexity

• 모든 경우: O(N logN) 

 

code (Python)

def merge_sort(list):
	if len(list) <= 1:
    	return list
        
    mid = len(list) // 2
	left = merge_sort(list[:mid])
    right = merge_sort(list[mid:])
        
    return merge(left, right)
    

def merge(left, right):
	result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
    	if (left[i] <= right[j]): # stable sort
        	result.append(left[i])
           	i += 1
        else:
        	result.append(right[j])
            j += 1
    	
    result.extend(left[i:])
    result.extend(right[j:])
    return result

code (C++)

void merge(int arr[], int left, int right, int mid) {
	int n1 = mid - left + 1;
	int n2 = right - mid;
    
    int *L = new int[n1];
    int *R = new int[n2];
    
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
    	if (L[i] <= R[j]) 
        	arr[k++] = L[i++];
        else 
        	arr[k++] = R[i++];
    }	
    
    while (i < n1) 
    	arr[k++] = L[i++];	
	while (j < n2)
    	arr[k++] = R[j++];
        
    delete[] L;
    delete[] R;
}

void merge_sort(int arr[], int left, int right) {
    
    if (left >= right) return;
        
    int mid = (left + right) / 2;
    
    merge_sort(arr, left, mid);
    merge_sort(arr, mid, right);
    merge(arr, left, mid, right);
}

 

 

4. Quick Sort

동작 방식

Quick Sort는 분할 정복(Divide & Conquer) 기반 정렬.

 

1.피벗(pivot) 선택

• 배열에서 하나의 원소를 피벗으로 정함 (보통 첫 원소, 마지막 원소, 중간값, 랜덤 등)

2. 분할(Partition)

• 피벗보다 작거나 같은 원소들을 한쪽 그룹
• 피벗보다 큰 원소들을 다른 쪽 그룹으로 나눔
• 분할이 끝나면:
  • 피벗은 최종 위치에 가 있고
  • 피벗 왼쪽은 모두 피벗 이하
  • 피벗 오른쪽은 모두 피벗 이상

3. 재귀 호출

• 피벗 기준으로 나뉜 왼쪽 구간과 오른쪽 구간에 대해
• 각각 다시 Quick Sort 재귀 호출
• 구간 크기가 0 또는 1이면 그대로 종료

이 과정을 반복하면 전체 배열이 정렬된다

Time Complexity

 

• 평균: O(n log n)
• 최악의 경우: O(n²)
  (이미 거의 정렬된 배열에서 나쁜 피벗을 고르면)
• in-place 정렬 가능
• 일반적인 구현은 unstable

code (Python)

def partition(A, left, right):

	pivot = A[left]
    low = left + 1
    high = right
    
    while low < high:
    	while low <= right and A[low] <= pivot:
        	low += 1
        while high >= left and A[high] > pivot:
        	high -= 1
        if low < high:
        	A[low], A[high] = A[high], A[low]
    
    A[left], A[high] = A[high], A[left]

	return high
    
deq quick_sort(A, left, right):
	if left < right:
    	q = partition(A, left, right)
        quick_sort(A, left, q-1)
        quick_sort(A, q+1, right)

code (C++)

int partition(int arr[], int left, int right) {
    int pivot = arr[right];      // 마지막 원소를 피벗으로 사용
    int i = left - 1;            // 피벗보다 작은 구간의 끝 인덱스

    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {   // 피벗보다 작거나 같으면 왼쪽으로 보냄
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    // 피벗을 자기 자리로 이동
    std::swap(arr[i + 1], arr[right]);
    return i + 1;                // 피벗의 최종 위치
}

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;

    int p = partition(arr, left, right); // 분할
    quickSort(arr, left, p - 1);         // 왼쪽 구간
    quickSort(arr, p + 1, right);        // 오른쪽 구간
}

 

 

 

5. Counting Sort (Linear-Time Sorting)

 

Counting Sort는 각 키가 정수이고, 작은 범위 안에 있을 때 사용할 수 있는 선형 시간 정렬이다 

 

동작 방식

 

• 정렬할 배열 A[0..n-1] 의 값들이 0 ~ k 범위라고 하자.
• 크기 k+1짜리 배열 C[0..k]를 만들고 전부 0으로 초기화.
• A를 한 번 보면서 각 값이 몇 번 나왔는지 카운트.
• C를 누적합(prefix sum)으로 바꿔서
  C[v] = v 이하 원소의 개수가 되게 만든다.
• 뒤에서부터 보면서 제자리를 찾아 넣기 (이때 stable).

 

 

Time Complexity

• 시간 복잡도: O(n + k) (n = 원소 개수, k = 값 범위)
• 공간 복잡도: O(n + k)
• 정수/작은 범위에만 사용 가능 (범위 크면 비효율)
• 위 구현처럼 하면 stable 정렬 됨

 

code (Python)

def counting_sort(list):
    output = [0] * (len(list))
    count = [0] * (max(list) + 1)
    
    for i in range(len(list)):
    	count[list[i]] += 1
       
    for i in range(1, len(count)):
    	count[i] += count[i-1]
    
    for i in range(len(list)):
    	j = len(list) - 1 - i
        count[list[j]] -= 1
        index = count[list[j]]
        output[index] = list[j]
        
   	return output