c 언어 데이터 구조 과목 설정 정렬 알고리즘 비교
7013 단어 데이터 구조
typedef int ElementType; void SetFigure (int * arr, int len) {FILE * fp = fopen ("rand. txt", "w"); / / 무 작위 수 를 생 성하 고 파일 을 기록 합 니 다.
int i; srand(time(NULL)); for (i = 0; i { arr[i]=rand(); fprintf(fp,"%d ",arr[i]); } fclose(fp); }
void GetFigure (int * arr, int len) / / 무 작위 수 를 읽 고 arr [] {FILE * fp = fopen ("rand. txt", "r"); int i; for (i = 0; i < len; i + +) {fscanf (fp, "% d", arr + i);} fclose (fp);}
void Print (int * arr, int len) / / 출력 이 배 열 된 데이터 {int i; for (i = 0; i {printf ("% d", arr [i]);}
}
void swap 01 (int * arr, int i, int j) / 두 변수의 값 {int temp = arr [i]; arr [i] = arr [j]; arr [j] = temp;}
void Bubbling (int * arr, int len) / / 거품 정렬 {int i; int j; int temp;
for(i = 0; i < len - 1; i++)
{
for(j = 0; j < len - 1 - i; j++)
{
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void SelectionSort (int arr, int len) / / O (nn) 정렬 선택 {int i = 0; int j = 0; int k = - 1;
for(i=0; i}
void InertionSort (int arr, int len) / / O (nn) 정렬 {int i = 0; int j = 0; int k = - 1; int temp = - 1;
for(i=1; i=0) && (arr[j]>temp); j--)
{
arr[j+1] = arr[j]; //
k = j; //k
}
arr[k] = temp;//
}
}
void ShellSort (int * arr, int len) / / 힐 정렬 {int i = 0; int j = 0; int k = - 1; int temp = - 1; int gap = len; do {
gap = gap / 3 + 1; //O（n 1.3）
for(i=gap; i=0) && (arr[j]>temp); j-=gap)
{
arr[j+gap] = arr[j];
k = j;
}
arr[k] = temp;
}
}while( gap > 1 );
}
void swap 1 (int * arr, int i, int j) {int temp = arr [i]; arr [i] = arr [j]; arr [j] = temp;} / / 구분 과정의 첫 번 째 요 소 는 중심 축 으로 2 개의 유효한 하위 서열 int partition (int * arr, int low, int high) {int pv = arr [low] 로 나 뉜 다.
while( low < high )
{
while( (low < high) && (arr[high] >= pv) )
{
high--; // ， ， high
}
swap1(arr, low, high);
while( (low < high) && (arr[low] <= pv) )
{
low++;
}
swap1(arr, low, high);
}
// 。。。
return low;
}
/ / n 개의 요 소 를 이에 따라 1 개의 요소 로 줄 일 때 1 개의 요 소 는 질서 있 는 서열 로 볼 수 있 기 때 문 입 니 다.
void QSort2(int *arr, int low, int high) { if( low < high ) { int pivot = partition(arr, low, high);
// 1
QSort2(arr, low, pivot-1);
// 2
QSort2(arr, pivot+1, high);
}
}
void QSort(int *arr, int low, int high) { if( low < high ) { int pivot = partition(arr, low, high);
// 1
QSort2(arr, low, pivot-1);
// 2
QSort2(arr, pivot+1, high);
}
}
void QuickSort(int arr, int len) // O(nlogn) { QSort(arr, 0, len-1); }
void PercDown(int *arr, int i, int N) { int child; ElementType Tmp;
for (Tmp = arr[i]; 2*i+1 < N; i = child){
child = 2*i+1; // 0 ， 2*i
if (child != N - 1 && arr[child + 1] > arr[child])
++child; //
if (Tmp < arr[child])
arr[i] = arr[child];
else
break;
}
arr[i] = Tmp;
}
void HeapSort (int * arr, int N) {int i; for (i = N / 2; i > = 0; -- i) PercDown (arr, i, N); / / 구조 더미 for (i = N - 1; i > 0; – i) {swap 1 (arr, 0, i); / / 최대 요소 (뿌리) 를 배열 의 끝 요소 와 교환 하여 가장 큰 요 소 를 삭제 하고 PercDown (arr, 0, i) 을 재 구성 합 니 다.}}
void radix Sort (int * arr, int len) {int i; void innerCounting Sort (int * arr, int len, int d); / 내부 계수 정렬 성명 for (i = 0; i < WIDTH; i + +) {innerCounting Sort (arr, len, i); / / 모든 요소 의 한 사람 에 게 내부 계수 정렬 을 호출 합 니 다}}
void inner Counting Sort (int * arr, int len, int d) / / d 자릿수 에 따라 배열 을 정렬 합 니 다 {int i, j, k [MAXK] = {0}; / 배열 K 는 특정한 요소 의 개 수 를 통계 하 는 데 사 용 됩 니 다. 이 요 소 는 정렬 대기 배열 의 한 비트 의 수치 int * ip = (int *) malloc (len * sizeof (int); / / 정렬 대기 배열 의 요 소 를 저장 하 는 한 비트 의 수치 int * bp = (int *) malloc(len * sizeof (int); int getDValue (int value, int d); / / 정렬 할 배열 요소 의 d 위 값 for (i = 0; i < len; i +) {ip [i] = getDValue (arr [i], d); k [ip [i]] +;}
for (j = 1; j < MAXK; j++) // j
{
k[j] = k[j] + k[j-1];
}
for (i = len - 1; i >= 0; i--)// d ，
{
bp[k[ip[i]] - 1] = arr[i];
k[ip[i]]--;
}
for (i = 0; i < len; i++) //
{
arr[i] = bp[i];
}
free(ip);
free(bp);
}
int getDValue (int value, int d) / / 숫자 d 자리 의 값 을 가 져 옵 니 다. 자릿수 색인 은 0 부터 {for (; d > 0 & value > 0; d –) {value = value / MAXK;} return value% MAXK;}
int main () {int * arr = (int *) malloc (size of (int) * M); SetFigure (arr, M); / / 무 작위 수 를 기록 하고 파일 에 저장 합 니 다.
GetFigure (arr, M); clock t beg = clock (); Bubbling (arr, M); / / 거품 정렬 clock t end = clock (); printf ("거품 정렬 소요 시간:%. 2lfms", (end - beg) * 1000.0 / CLOCKS PER SEC); / / print (arr, M);
memset (arr, 0, sizeof (int) * M); / / 배열 GetFigure (arr, M) 초기 화; clock t beg 1 = clock (); selectionSort (arr, M); / / 정렬 clock t end 1 = clock (); printf ("정렬 선택 에 필요 한 시간 은%. 2lfms", (end 1 - beg 1) * 1000.0 / CLOCKS PER SEC); / / print (arr, M);
memset (arr, 0, sizeof (int) * M); / / 배열 GetFigure (arr, M) 초기 화; clock t beg 2 = clock (); InertionSort (arr, M); / / 정렬 clock t end 2 = clock () 삽입; printf ("정렬 을 직접 삽입 하 는 데 소요 되 는 시간 은:%. 2lfms", (end 2 - beg 2) * 1000.0 / CLOCKS PER SEC); / / print (arr, M);
memset (arr, 0, sizeof (int) * M); / / 배열 GetFigure (arr, M) 초기 화; clock t beg 3 = clock (); ShellSort (arr, M); / / 힐 정렬 clock t end 3 = clock (); printf ("힐 정렬 에 필요 한 시간 은%. 2lfms", (end3 - beg 3) * 1000.0 / CLOCKS PER SEC); / / print (arr, M);
memset (arr, 0, sizeof (int) * M); / / 배열 GetFigure (arr, M) 초기 화; clock t beg 4 = clock (); QuickSort (arr, M); / / 빠 른 정렬 clock t end 4 = clock (); printf ("빠 른 정렬 소요 시간:%. 2lfms", (end 4 - beg 4) * 1000.0 / CLOCKS PER SEC); / / print (arr, M);
memset (arr, 0, sizeof (int) * M); / / 배열 GetFigure (arr, M) 초기 화; clock t beg 5 = clock (); HeapSort (arr, M); / / 정렬 clock t end 5 = clock (); printf ("정렬 에 필요 한 시간 은%. 2lfms", (end 5 - beg 5) * 1000.0 / CLOCKS PER SEC); / / print (arr, M);
memset (arr, 0, sizeof (int) * M); / / 배열 GetFigure (arr, M) 초기 화; clock t beg 6 = clock (); radixSort (arr, M); / / 기수 정렬 clock t end 6 = clock (); printf ("기수 정렬 소요 시간:%. 2lfms", (end 6 - beg 6) * 100 / 0.0 CLOCKS PER SEC); / / print (arr, M); return 0;}
좋은 웹페이지 즐겨찾기
