Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5 3 8 9 2 7 4 1
Solution 합병 정렬 퀵 정렬 이동 회수는 총 48번 이유: mergeSort()가 총 3번 호출되고, 각 호출시에 임시배열에 배열 모든 요소가 이동하고, 다시 임시배열에서 원래 배열로 이동하므로, 8*2 = 16번의 이동이 일어난다. 총 3번 호출되므로 16*3 = 48번의 이동이 발생한다. 퀵 정렬 이동 회수는 총 24번 이유: 교환 회수가 총 8번 발생하고, 각 교환에 3번이 이동이 발생하므로 8*3 = 24번의 이동이 발생한다. 주의: 퀵정렬시 피봇 위치와 high의 위치가 동일한 경우에도 교환이 발생한다는 것에 유의. 사실 이러한 교환이 불필요하다. 알고리즘을 다음과 같이 수정하면 그러한 교환은 일어나지 않는다.
int partition(int list[], int left, int right) { int pivot, low, high; low = left; high = right+1; // low, high 위치 설정 // 비교 전에 low는 증가, high는 감소 pivot = list[left]; // 피봇은 첫번째 원소로 설정 return high; // 피봇 위치 반환 } do { // 피봇보다 작은 항목은 왼쪽으로, 큰 항목은 오른쪽으로 // 피봇보다 큰 항목을 찾는다. // 피봇보다 작은 항목을 찾는다 } while (low <high); // 피봇을 중앙에 위치 if (left != high) swap(a[left], a[high]);
review 퀵정렬시 불필요한 교환 제외하면 이동 회수는 18번. 이 경우에 -1 이동회수 과정 보이지 않으면 -3, 미흡하면 -2