|
QuickSort
정의
정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준값(Pivot)을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할
왼쪽 부분집합에는 기준값보다 작은 원소들을 이동
오른쪽 부분집합에는 기준값보다 큰 원소들을 이동
|
|
|
1; i <= high; i++)
if(S[i] < pivotitem) {
j++;
temp = S[i];
S[i] = S[j];
S[j] = temp;
}
pivotpoint = j;
temp = S[low];// pivotitem을 pivotpoint에 넣음.
S[low] = S[pivotpoint];
S[pivotpoint] = temp;
}
|
|
|
quicksort(list2, left, right);
qsum=qsum+count;
printf(" 퀵정렬: %d번 비교\n", count);
}
printf("\n선택정렬 평균비교횟수: %d번\n", ssum/10);
printf("퀵정렬 평균비교횟수: %d번\n", qsum/10);
} 1.53KB
|
|
|
|
/*Quicksort ! Pointer version with macros.*/
#define swap(x,y) {int t; t = x ; x = y ; y = t;}
#define order(x,y) if(x>y) swap(x,y)
#define o2(x,y) order(x,y)
#define o3(x,y,z) o2(x,y); o2(x,z); o2(y,z)
typedef enum {yes, no} yes_no;
static yes_no find_pivot(int *left, int *right, int *
|
|
|
QuickSort(ar,left); // 왼쪽 구간 정렬
QuickSort(ar+left+1,num-left-1); // 오른쪽 구간 정렬
}
** Worst Case (최악의 경우)
퀵 정렬의 최악의 경우는 입력배열 a의 원소들이 이미 오름차순(또는 내림차순)으로 정렬이 되어있는 경우이다. 만약 a가 이미 오름
|
|
메뉴펼치기
