합병 정렬(Merge Sort)이란? 배열을 2개의 하위 배열로 재귀적으로 나눈 후, 다시 각 배열을 합치면서 정렬한다. 분할 정복 (Divide and Conquer)에 해당한다. *분할 정복이란? 문제를 작게 분할한 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘 방법 주어진 배열을 균등한 크기의 2개의 배열로 분할한다. 분할된 부분 배열을 반복해서 2개의 배열로 분할한다. 더 이상 분할할 수 없을 때, 다시 2개의 배열을 합쳐서 정렬한다. ([3], [1] -> [1, 3]) 재귀적으로 정렬된 부분 배열을 하나로 합치면서 전체가 정렬된 배열을 만든다. ([1, 3], [2, 4] -> [1, 2, 3, 4]) 파이썬으로 구현하기 def merge_sort(arr, start, ..

퀵 정렬(Quick Sort)이란? 분할 정복 (Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘 *분할 정복 이란? 문제를 작게 분할한 후 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결하는 알고리즘 방법 피봇(pivot)이라는 값을 하나 정한다. (임의로 정할 수 있지만, 여기서는 중간에 있는 값을 하나 정해보자.) 피봇보다 작은 값을 left 배열에, 피봇보다 큰 값을 right 배열에 추가한다. left(피봇보다 작은 값들), 피봇, right(피봇보다 큰 값들) 로 만들어진다. left, right 배열에 대해 위 작업을 재귀적으로 반복한다. 파이썬으로 구현하기 방법1 pivot 보다 작은 값을 왼쪽 배열에, 큰 값을 오른쪽 배열에 추가한다. 각 배열에 대해 ..