![]()
Quick Sort 문제를 2개의 부분 문제로 분할 각 부분 문제의 크기가 일정하지 않음 Idea 피봇 (pivot)을 임의로 설정하여 피봇보다 작은 숫자는 피봇 기준 왼쪽편으로, 피봇보다 큰 숫자는 피봇 기준 오른쪽으로 위치하도록 분할하고 피봇을 그 사이에 놓는다. 분할된 부분 문제들에서도 재귀적으로 수행 문제가 2개로 분할되고, 부분 문제의 크기가 1/2로 감소하는 알고리즘 Pseudo code QuickSort(A, left, right) Input: Array A[left] ~ A[right] Output: Sorted Array A[left] ~ A[right] if (left < right) { p := partition(A, left, right) QuickSort(A, left, p) //..
![]()
합병정렬 (Merge Sort) 문제가 2개로 분할되고, 부분 문제의 크기가 1/2로 감소하는 알고리즘 합병 (Merge) 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자로 합치는 것 Example Array A: 6, 14, 18, 20, 29 Array B: 1, 2, 15, 25, 30, 45 Array C: 1, 2, 6, 14, 15, 18, 20, 25, 29, 30, 45 Pseudo code MergeSort(A, start, end) Input: A[start] ~ A[end] Output: Sorted A[start] ~ A[end] if (start < end) { // 배열의 원소의 수가 2개 이상이면 k = (start + end) / 2 // k는 반으로 나누기 위한 중간 원소의..
