для удаления 4 худших значений из 8 выборок
Методы описаны для geeksforgeeks k самых больших (или самых маленьких) элементов в массиве , и вы может реализовать лучший метод, который вам подходит.
Я решил использовать этот хороший сайт для генерации лучшего алгоритма сортировки с макросами SWAP(), необходимыми для сортировки массива из 8 элементов. Затем я создал небольшую C программу, которая будет проверять любую комбинацию из 8 элементов массива в моей функции сортировки. Затем, поскольку мы заботимся только о группах из 4 элементов, я сделал что-то грубое - для каждого из макросов SWAP() я попытался прокомментировать макрос и посмотреть, будет ли программа по-прежнему успешной. Я мог бы прокомментировать 5 SWAP макросов, оставив 14 сравнений, необходимых для идентификации наименьших 4 элементов в массиве из 8 выборок.
/**
* Sorts the array, but only so that groups of 4 matter.
* So group of 4 smallest elements and 4 biggest elements
* will be sorted ok.
* s[0]...s[3] will have lowest 4 elements
* so they have to be "deleted"
* s[4]...s[7] will have the highest 4 values
*/
void sort_but_4_matter(int s[8]) {
#define SWAP(x, y) do { \
if (s[x] > s[y]) { \
const int t = s[x]; \
s[x] = s[y]; \
s[y] = t; \
} \
} while(0)
SWAP(0, 1);
//SWAP(2, 3);
SWAP(0, 2);
//SWAP(1, 3);
//SWAP(1, 2);
SWAP(4, 5);
SWAP(6, 7);
SWAP(4, 6);
SWAP(5, 7);
//SWAP(5, 6);
SWAP(0, 4);
SWAP(1, 5);
SWAP(1, 4);
SWAP(2, 6);
SWAP(3, 7);
//SWAP(3, 6);
SWAP(2, 4);
SWAP(3, 5);
SWAP(3, 4);
#undef SWAP
}
/* -------- testing code */
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int cmp_int(const void *a, const void *b) {
return *(const int*)a - *(const int*)b;
}
void printit_arr(const int *arr, size_t n) {
printf("{");
for (size_t i = 0; i < n; ++i) {
printf("%d", arr[i]);
if (i != n - 1) {
printf(" ");
}
}
printf("}");
}
void printit(const char *pre, const int arr[8],
const int in[8], const int res[4]) {
printf("%s: ", pre);
printit_arr(arr, 8);
printf(" ");
printit_arr(in, 8);
printf(" ");
printit_arr(res, 4);
printf("\n");
}
int err = 0;
void test(const int arr[8], const int res[4]) {
int in[8];
memcpy(in, arr, sizeof(int) * 8);
sort_but_4_matter(in);
// sort for memcmp below
qsort(in, 4, sizeof(int), cmp_int);
if (memcmp(in, res, sizeof(int) * 4) != 0) {
printit("T", arr, in, res);
err = 1;
}
}
void test_all_combinations() {
const int result[4] = { 0, 1, 2, 3 }; // sorted
const size_t n = 8;
int num[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };
for (size_t j = 0; j < n; j++) {
for (size_t i = 0; i < n-1; i++) {
int temp = num[i];
num[i] = num[i+1];
num[i+1] = temp;
test(num, result);
}
}
}
int main() {
test_all_combinations();
return err;
}
Проверено на кресте . sort_but_4_matter с g cc -O2 на x86_64 компилируется менее чем в 100 инструкций.