🗃️ 정렬

>> 정렬1 (선택, 버블, 계수 정렬)

합병 정렬 Merge Sort

: 반으로 나눠(Divide) 각각 정렬한 다음(Conquer) 병합하는 작업(Combine)을 반복하는 정렬 (안정 정렬)

→ 시간복잡도 O(n log n)

• Java

static void mergeSort(int[] arr, int start, int end) {
	// base case
	if(start >= end) return;
    
    // Divide
    int mid = (start + end) / 2;
    // recursive case
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    
	// 왼족 부분 임시 저장
    int[] temp = new int[arr.length];
    int i;
    int t = 0;
    for(i = start; i <= mid; i++) {
    	temp[t++] = arr[i];
    }
    
    // Conquer
    int sorted = start;
    int j = 0;
    while(i <= end && j < t) {
    	arr[sorted++] = (temp[j] <= arr[i]) ? temp[j++]: arr[i++];
    }
    
    // 왼쪽 부분 남은 요소 뒤에 복사
    while(j < t) {
    	arr[sorted++] = temp[j++];
    }
}

• Python

def merge(list1, list2):
    merged_list = []
    i = 0
    j = 0
    
    # Conquer & Combine
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            merged_list.append(list1[i])
            i += 1
        else:
            merged_list.append(list2[j])
            j += 1
            
    # 남은 요소 뒤에 추가    
    if i < len(list1):
        merged_list += list1[i:]
    elif j < len(list2):
        merged_list += list2[j:]
        
    return merged_list

# 합병 정렬
def merge_sort(my_list):
    # base case
    if len(my_list) <=  1:
        return my_list
        
    # Divide
    mid = len(my_list) // 2
    
    # recursive case
    return merge(merge_sort(my_list[:mid]), merge_sort(my_list[mid:]))

 

---

퀵 정렬 Quick Sort

: 임의로 설정된 Pivot을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 나누는 비교 정렬

→ 시간복잡도 O(n log n) (최악의 경우 O(n^2))

• Java

// 두 요소의 위치를 바꿔주는 함수
static void swap(int[] arr, int idx1, int idx2) {
	int temp = arr[idx1];
    arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

// 퀵 정렬
static void quickSort(int[] arr, int start, int end) {
	// base case
    if(end <= start) return;
    
    // pivot 설정
    int left = start;
    int right = end;
    int pivot = arr[(left + right) / 2];	// 중간 요소로 설정
    
    // partition
    while(left <= right) {
    	while(arr[left] < pivot) left++;
        while(arr[right] > pivot) right--;
        
        if(left <= right) swap(arr, left++, right--);
    }
    
    // recursive case
    quickSort(arr, start, right);
    quickSort(arr, left, end);
}

• Python

# 두 요소의 위치를 바꿔주는 함수
def swap(my_list, idx1, idx2):
    my_list[idx1], my_list[idx2] = my_list[idx2], my_list[idx1]
    return my_list

# pivot을 기준으로 나누는 함수
def partition(my_list, start, end):
	pivot = end
    i = start
    left = start
    
    while i < pivot:
        if my_list[pivot] > my_list[i]:
            swap(my_list, i, left)
            left += 1
        i += 1
            
    swap(my_list, pivot, left)
    pivot = left
        
    return pivot
    
# 퀵 정렬
def quicksort(my_list, start, end):
	# base case
    if end <= start:
        return

    # pivot 설정
    pivot = partition(my_list, start, end)	// 중간 인덱스로 설정

    # recursive case (pivot의 왼쪽, 오른쪽 부분 정렬)
    quicksort(my_list, start, pivot - 1)
    quicksort(my_list, pivot + 1, end)