C 자료구조/Sort Advanced
-
Quick SortC 자료구조/Sort Advanced 2020. 6. 22. 17:57
퀵 정렬도 분할 정복 방법에 근거한다. 여기서 정렬방식은 오름차순 기준이다. 퀵 정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각 각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용한다. 그러나, 병합 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비 균등하게 분할한다. 먼저, 리스트 안에 있는 한 요소를 피봇으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피봇으로 하기로 한다. 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮겨지고 피봇보다 큰 요소들은 모두 피봇의 오른쪽으로 옮겨진다. 결과적으로 피봇을 중심으로 왼쪽은 피봇보다 작은 요소들로 구성되고, 오른쪽은 피봇보다 큰 요소들로 구성된다. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리..
-
1. Merge SortC 자료구조/Sort Advanced 2020. 6. 21. 18:11
간단한 도식화 그림을 살펴보자. 위의 도식화 그림을 설명하면 아래와 같다. 위의 그림과 같이 정렬할 배열이 주어졌다고 가정하면, 1. 분할 : 정렬할 배열을 27 10 12 20 과 25 13 15 22의 2개의 부분 배열로 나눈다. 2. 정복 : 부분 배열을 정렬하여 10 12 20 27 과 13 15 22 25를 얻는다. 3. 결합 : 부분 배열을 통합하여 10 12 13 15 20 22 25 27 을 얻는다. 각 각의 부분 배열들을 어떻게 정렬하여야 할까? 정답은 부분 배열들을 정렬할 때도 합병 정렬을 순환적으로 적용하면 된다. 즉, 위의 예에서 부분 배열인 27 10 12 20을 정렬할 때도 합병 정렬의 개념을 다시 적용한다. 이는 합병 정렬 함수의 순환적인 호출을 이용하여 구현하면 된다. 위의 ..