가치투자자

퀵 정렬 (Quick Sort) 1. 퀵 정렬이란? 퀵 정렬(quick sort) 역시 병합 정렬과 마찬가지로 어떤 문제를 2개의 작은 문제로 분리해 각각을 해결하는 분할 정복 알고리즘 중 하나다. 1-1) 차이점 병합 정렬 - 분할 단계에서는 분할만 하고 병합 단계에서 정렬을 한다 퀵 정렬 - 분할 단계에서 정렬이 이루어지며, 병합 시에는 병합만 한다. 퀵 정렬 알고리즘은 다음 개념들을 바탕으로 진행된다. 분할 (Divde) : 입력된 배열을 기준점(pivot)을 기준으로 비균등하게 분할한다. 정복 (Conquer) : 분할된 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(리스트의 길이가 1이 아니면) 순환 호출을 이용하여 다시 분할한다. 결합 (Combine) : 정렬된 부분 배열들을..

병합 정렬 (merge sort) 1. 병합 정렬이란? 병합 정렬(merge sort)은 어떤 문제를 2개의 작은 문제로 분리해 각각 해결한 다음, 이걸 모아서 원래 문제를 해결하는 분할 정복 알고리즘 중 하나다. 병합 정렬 알고리즘은 다음 개념들을 바탕으로 진행된다. 분할(Divide) : 입력된 배열을 같은 크기의 부분 배열 2개로 분할한다. 정복(Conquer) : 부분 배열의 크기가 충분히 작지 않으면(리스트의 길이가 0 또는 1이 아니면) 다시 분할을 한다. 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 병합한다. 병합 정렬은 다음 단계들로 진행된다. 부분 배열의 요소들을 결합할 빈 배열이 필요하다. 부분 배열의 크기(length)가 1이 될 때까지 쪼개준다. 부분 배열의 0번째..