알고리즘 도론 코드 제9장 중위수와 순서 통계학
제9장 중위수와 순서통계학
9.1 최소값 및 최대값
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
int minimum(int A[], int n)
{
int min = A[0];
for (int i = 1; i < n; i++) {
if (min > A[i]) {
min = A[i];
}
}
return min;
}
void min_and_max(int A[], int n, int *min, int *max)
{
int i;
if (n % 2 == 1) {
*min = A[0];
*max = A[0];
i = 1;
} else {
if (A[0] > A[1]) {
*max = A[0];
*min = A[1];
} else {
*max = A[1];
*min = A[0];
}
i = 2;
}
for (; i < n; i += 2) {
if (A[i] > A[i + 1]) {
if (A[i] > *max) {
*max = A[i];
}
if (A[i + 1] < *min) {
*min = A[i + 1];
}
} else {
if (A[i + 1] > *max) {
*max = A[i + 1];
}
if (A[i] < *min) {
*min = A[i];
}
}
}
}
void print_array(int a[], int n)
{
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("
");
}
int main()
{
srand((unsigned)time(NULL));
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = rand() % 100;
}
print_array(a,10);
printf(" :%d
",minimum(a,10));
int min;
int max;
min_and_max(a,10,&min,&max);
printf(" :%d,%d
",min,max);
}
9.2 기대 선형 시간으로 선택
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void swap(void *a, void *b, size_t elem_size)
{
if(a==NULL||b==NULL||a==b)
return;
char temp[elem_size]; /* */
memcpy(temp, a, elem_size);
memcpy(a, b, elem_size);
memcpy(b, temp, elem_size);
}
int partition(void *base, size_t elem_size, int p, int r,
int (*comp) (const void *, const void *))
{
char *cbase = base;
void *key = &cbase[r * elem_size];
int i = p - 1;
for (int j = p; j < r; j++) {
if (comp(&cbase[j * elem_size], key) <= 0) {
++i;
swap(&cbase[i * elem_size], &cbase[j * elem_size],
elem_size);
}
}
swap(&cbase[(i + 1) * elem_size], key, elem_size);
return i + 1;
}
int randomized_partition(void *base, size_t elem_size, int p, int r,
int (*comp) (const void *, const void *))
{
char *cbase = base;
int i = rand() % (r - p + 1) + p;
swap(&cbase[r * elem_size], &cbase[i * elem_size], elem_size);
return partition(base, elem_size, p, r, comp);
}
void *randomized_select(void *base, size_t elem_size, int p, int r, int i,
int (*comp) (const void *, const void *))
{
char *cbase = base;
if (p == r)
return &cbase[p * elem_size];
int q = randomized_partition(base, elem_size, p, r, comp);
int k = q - p + 1;
if (i == k) {
return &cbase[q * elem_size];
} else if (i < k) {
return randomized_select(base, elem_size, p, q - 1, i, comp);
} else {
return randomized_select(base, elem_size, q + 1, r, i - k,
comp);
}
}
void print_array(int a[], int length)
{
for (int i = 0; i < length; i++) {
printf("%d ", a[i]);
}
printf("
");
}
int cmp_int(const void *p1, const void *p2)
{
const int *pa = p1;
const int *pb = p2;
if (*pa < *pb)
return -1;
if (*pa == *pb)
return 0;
return 1;
}
void randomize_quick_sort(void *base, size_t elem_size, int p, int r,
int (*comp) (const void *, const void *))
{
if (p < r) {
int q = randomized_partition(base, elem_size, p, r, comp);
randomize_quick_sort(base, elem_size, p, q - 1, comp);
randomize_quick_sort(base, elem_size, q + 1, r, comp);
}
}
int main()
{
srand((unsigned)time(NULL));
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = rand() % 100;
}
printf(" :
");
print_array(a, 10);
int order = 3;
int *select_value = randomized_select(a, sizeof(int), 0, 9, order, cmp_int);
randomize_quick_sort(a, sizeof(int),0,9, cmp_int);
printf(" %d :%d
", order, *select_value);
printf(" :%s
",
*select_value == a[order - 1] ? " " : " ");
return 0;
}
9.3 최악의 경우 선형 시간의 선택
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void insertion_sort(void *base, size_t elem_size, size_t n,
int (*comp) (const void *, const void *))
{
char *cbase = base;
char key[elem_size];
for (size_t i = 1; i < n; i++) {
memcpy(key, &cbase[i * elem_size], elem_size);
/* base[i] base[0..i-1] */
int j = i - 1;
while (j >= 0 && comp(&cbase[j * elem_size], key) > 0) {
memcpy(&cbase[(j + 1) * elem_size],
&cbase[j * elem_size], elem_size);
j--;
}
memcpy(&cbase[(j + 1) * elem_size], key, elem_size);
}
}
void swap(void *a, void *b, size_t elem_size)
{
if (a == NULL || b == NULL || a == b)
return;
char temp[elem_size]; /* */
memcpy(temp, a, elem_size);
memcpy(a, b, elem_size);
memcpy(b, temp, elem_size);
}
int partition(void *base, size_t elem_size, int p, int r, void *pivot,
int (*comp) (const void *, const void *))
{
char *cbase = base;
void *key = pivot;
int i = p - 1;
int pivot_pos = p; /* */
for (int j = p; j < r; j++) {
if (comp(&cbase[j * elem_size], key) == 0)
pivot_pos = j; /* */
if (comp(&cbase[j * elem_size], key) <= 0) {
++i;
swap(&cbase[i * elem_size], &cbase[j * elem_size],
elem_size);
}
}
swap(&cbase[(i + 1) * elem_size], &cbase[pivot_pos * elem_size],
elem_size);
return i + 1;
}
void *select(void *base, size_t elem_size, int p, int r, int order,
int (*comp) (const void *, const void *))
{
char *cbase = base;
if (p == r)
return &cbase[p * elem_size];
int n = r - p + 1;
int array_count = n % 5 == 0 ? n / 5 : n / 5 + 1;
char array[elem_size * array_count];
for (int i = 0; i < array_count; i++) {
int begin = p + i * 5;
int end = begin + 4 < r ? begin + 4 : r;
insertion_sort(&cbase[begin * elem_size], elem_size,
end - begin + 1, comp);
int middle=begin+(end-begin)/2;
memcpy(&array[i * elem_size], &cbase[middle * elem_size],
elem_size);
}
void *x =
select(array, elem_size, 0, array_count - 1, (array_count + 1) / 2,
comp);
/* x A， */
int q = partition(base, elem_size, p, r, x, comp);
int k = q - p + 1;
if (order == k) {
return &cbase[q * elem_size];
} else if (order < k) {
return select(base, elem_size, p, q - 1, order, comp);
} else {
return select(base, elem_size, q + 1, r, order - k, comp);
}
}
void print_array(int a[], int length)
{
for (int i = 0; i < length; i++) {
printf("%d ", a[i]);
}
printf("
");
}
int cmp_int(const void *p1, const void *p2)
{
const int *pa = p1;
const int *pb = p2;
if (*pa < *pb)
return -1;
if (*pa == *pb)
return 0;
return 1;
}
int main()
{
srand((unsigned)time(NULL));
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = rand() % 100;
}
printf(" :
");
print_array(a, 10);
int order = 3;
int *select_value = select(a, sizeof(int), 0, 9, order, cmp_int);
insertion_sort(a, sizeof(int), 10, cmp_int);
printf(" %d :%d
", order, *select_value);
printf(" :%s
",
*select_value == a[order - 1] ? " " : " ");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
int minimum(int A[], int n)
{
int min = A[0];
for (int i = 1; i < n; i++) {
if (min > A[i]) {
min = A[i];
}
}
return min;
}
void min_and_max(int A[], int n, int *min, int *max)
{
int i;
if (n % 2 == 1) {
*min = A[0];
*max = A[0];
i = 1;
} else {
if (A[0] > A[1]) {
*max = A[0];
*min = A[1];
} else {
*max = A[1];
*min = A[0];
}
i = 2;
}
for (; i < n; i += 2) {
if (A[i] > A[i + 1]) {
if (A[i] > *max) {
*max = A[i];
}
if (A[i + 1] < *min) {
*min = A[i + 1];
}
} else {
if (A[i + 1] > *max) {
*max = A[i + 1];
}
if (A[i] < *min) {
*min = A[i];
}
}
}
}
void print_array(int a[], int n)
{
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("
");
}
int main()
{
srand((unsigned)time(NULL));
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = rand() % 100;
}
print_array(a,10);
printf(" :%d
",minimum(a,10));
int min;
int max;
min_and_max(a,10,&min,&max);
printf(" :%d,%d
",min,max);
}#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void swap(void *a, void *b, size_t elem_size)
{
if(a==NULL||b==NULL||a==b)
return;
char temp[elem_size]; /* */
memcpy(temp, a, elem_size);
memcpy(a, b, elem_size);
memcpy(b, temp, elem_size);
}
int partition(void *base, size_t elem_size, int p, int r,
int (*comp) (const void *, const void *))
{
char *cbase = base;
void *key = &cbase[r * elem_size];
int i = p - 1;
for (int j = p; j < r; j++) {
if (comp(&cbase[j * elem_size], key) <= 0) {
++i;
swap(&cbase[i * elem_size], &cbase[j * elem_size],
elem_size);
}
}
swap(&cbase[(i + 1) * elem_size], key, elem_size);
return i + 1;
}
int randomized_partition(void *base, size_t elem_size, int p, int r,
int (*comp) (const void *, const void *))
{
char *cbase = base;
int i = rand() % (r - p + 1) + p;
swap(&cbase[r * elem_size], &cbase[i * elem_size], elem_size);
return partition(base, elem_size, p, r, comp);
}
void *randomized_select(void *base, size_t elem_size, int p, int r, int i,
int (*comp) (const void *, const void *))
{
char *cbase = base;
if (p == r)
return &cbase[p * elem_size];
int q = randomized_partition(base, elem_size, p, r, comp);
int k = q - p + 1;
if (i == k) {
return &cbase[q * elem_size];
} else if (i < k) {
return randomized_select(base, elem_size, p, q - 1, i, comp);
} else {
return randomized_select(base, elem_size, q + 1, r, i - k,
comp);
}
}
void print_array(int a[], int length)
{
for (int i = 0; i < length; i++) {
printf("%d ", a[i]);
}
printf("
");
}
int cmp_int(const void *p1, const void *p2)
{
const int *pa = p1;
const int *pb = p2;
if (*pa < *pb)
return -1;
if (*pa == *pb)
return 0;
return 1;
}
void randomize_quick_sort(void *base, size_t elem_size, int p, int r,
int (*comp) (const void *, const void *))
{
if (p < r) {
int q = randomized_partition(base, elem_size, p, r, comp);
randomize_quick_sort(base, elem_size, p, q - 1, comp);
randomize_quick_sort(base, elem_size, q + 1, r, comp);
}
}
int main()
{
srand((unsigned)time(NULL));
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = rand() % 100;
}
printf(" :
");
print_array(a, 10);
int order = 3;
int *select_value = randomized_select(a, sizeof(int), 0, 9, order, cmp_int);
randomize_quick_sort(a, sizeof(int),0,9, cmp_int);
printf(" %d :%d
", order, *select_value);
printf(" :%s
",
*select_value == a[order - 1] ? " " : " ");
return 0;
}#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void insertion_sort(void *base, size_t elem_size, size_t n,
int (*comp) (const void *, const void *))
{
char *cbase = base;
char key[elem_size];
for (size_t i = 1; i < n; i++) {
memcpy(key, &cbase[i * elem_size], elem_size);
/* base[i] base[0..i-1] */
int j = i - 1;
while (j >= 0 && comp(&cbase[j * elem_size], key) > 0) {
memcpy(&cbase[(j + 1) * elem_size],
&cbase[j * elem_size], elem_size);
j--;
}
memcpy(&cbase[(j + 1) * elem_size], key, elem_size);
}
}
void swap(void *a, void *b, size_t elem_size)
{
if (a == NULL || b == NULL || a == b)
return;
char temp[elem_size]; /* */
memcpy(temp, a, elem_size);
memcpy(a, b, elem_size);
memcpy(b, temp, elem_size);
}
int partition(void *base, size_t elem_size, int p, int r, void *pivot,
int (*comp) (const void *, const void *))
{
char *cbase = base;
void *key = pivot;
int i = p - 1;
int pivot_pos = p; /* */
for (int j = p; j < r; j++) {
if (comp(&cbase[j * elem_size], key) == 0)
pivot_pos = j; /* */
if (comp(&cbase[j * elem_size], key) <= 0) {
++i;
swap(&cbase[i * elem_size], &cbase[j * elem_size],
elem_size);
}
}
swap(&cbase[(i + 1) * elem_size], &cbase[pivot_pos * elem_size],
elem_size);
return i + 1;
}
void *select(void *base, size_t elem_size, int p, int r, int order,
int (*comp) (const void *, const void *))
{
char *cbase = base;
if (p == r)
return &cbase[p * elem_size];
int n = r - p + 1;
int array_count = n % 5 == 0 ? n / 5 : n / 5 + 1;
char array[elem_size * array_count];
for (int i = 0; i < array_count; i++) {
int begin = p + i * 5;
int end = begin + 4 < r ? begin + 4 : r;
insertion_sort(&cbase[begin * elem_size], elem_size,
end - begin + 1, comp);
int middle=begin+(end-begin)/2;
memcpy(&array[i * elem_size], &cbase[middle * elem_size],
elem_size);
}
void *x =
select(array, elem_size, 0, array_count - 1, (array_count + 1) / 2,
comp);
/* x A， */
int q = partition(base, elem_size, p, r, x, comp);
int k = q - p + 1;
if (order == k) {
return &cbase[q * elem_size];
} else if (order < k) {
return select(base, elem_size, p, q - 1, order, comp);
} else {
return select(base, elem_size, q + 1, r, order - k, comp);
}
}
void print_array(int a[], int length)
{
for (int i = 0; i < length; i++) {
printf("%d ", a[i]);
}
printf("
");
}
int cmp_int(const void *p1, const void *p2)
{
const int *pa = p1;
const int *pb = p2;
if (*pa < *pb)
return -1;
if (*pa == *pb)
return 0;
return 1;
}
int main()
{
srand((unsigned)time(NULL));
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = rand() % 100;
}
printf(" :
");
print_array(a, 10);
int order = 3;
int *select_value = select(a, sizeof(int), 0, 9, order, cmp_int);
insertion_sort(a, sizeof(int), 10, cmp_int);
printf(" %d :%d
", order, *select_value);
printf(" :%s
",
*select_value == a[order - 1] ? " " : " ");
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
