algorithm2 Quick sort 퀵 정렬 - 주어진 배열을 피벗(pivot) 을 기준으로 작은 원소들은 왼쪽, 큰 원소들을 오른쪽으로 위치시킨다. - 이렇게 나뉜 두 개의 배열을 같은 반복을 반복하여 정렬한다. - 특정 기준을 바탕으로 배열을 나눈다는 점에서 병합정렬과는 차이가 있다. 또한, 병합 정렬의 경우 각 부분의 정렬이 끝난 후 병합 처리를 해줘야 하는 반면, 퀵 정렬은 추가적인 작업이 필요하지 않다. - 평균적으로 O(n log n)의 시간복잡도를 가진다. 과정 - Pivot을 배열의 가장 왼쪽으로 잡냐(Hoare-Partition) 혹은 오른쪽으로 잡냐(Lomuto-Partition) 에 따라 과정에 차이가 있을 수 있다. - Hoare-Partition을 기준으로 설명한다. - Pivot은 가장 왼쪽에 위치하며, 두 개의 .. 2021. 10. 9. Merge sort Merge sort (병합 정렬) - 병합 정렬이란, 여러 개의 정렬된 자료의 집합을 병합하여 하나의 정렬된 집합으로 만드는 방식이다. - 자료를 최소 단위의 문제까지 나눈 후, 차례대로 정렬하여 최종 정렬 결과를 얻어내는 분할정복 알고리즘을 활용한다. - O(n log n) 의 시간복잡도를 가진다. 과정 - 배열을 병합 정렬을 통해 정렬하는 과정을 살펴보자. - 우선 전체 배열에 대하여, 최소 크기의 부분집합이 될 때까지 분할작업을 계속한다. - 배열의 경우, 위 그림처럼 배열 안의 원소가 1개일 경우 최소 크기의 부분집합이 된다. - 분할 작업이 완료되면, 병합 단계에 들어간다. 각 2개의 부분집합을 정렬하면서, 하나의 집합으로 병합한다. - 최종적으로, 모든 부분집합이 1개로 병합될 때까지 반복한다.. 2021. 10. 9. 이전 1 다음
