Программный массив сортировки по остатку 3

Question

Меня попросили написать эффективную функцию со временем выполнения n, которая сортирует массив по оставшимся 3, программа помещает элементы, для которых остаток от деления на 3 равен 0, после элементов, что остаток равен 1, а затем 2, например.массив {7, 16, 3, 28, 12, 31, 14, 12} будет сортироваться таким образом {12, 3, 12, 28, 16, 31, 7, 14}, поэтому я пытаюсь написать эффективную функцию, ноон не охватывает все случаи и не работает для всех массивов

    int arr[] = { 7,16,3,28,12,31,14,12 };
    int rem0 = 0, rem1 = 1, rem2 = 2;

    for (int i = 0; i < 8; i++) {
        if (arr[i] % 3 == 0)
            rem0++;

        if (arr[i] % 3 == 1)
            rem1++;

        if (arr[i] % 3 == 2)
            rem2++;
    }

    int k = rem0, p = 0, m = 0 = 0;

    for (int i = 0; i < 8; i++) {
        while (rem0-k){
            swap(&arr[i], &arr[rem0 - k]);
            k--;
        }
        if (arr[i] % 3 == 1 && rem0+m<7) {
            swap(&arr[i], &arr[rem0 + m]);
            m++;
        }
        if (arr[i] % 3 == 1 && rem0 + rem1 + p<7) {
            swap(&arr[i], &arr[rem0+rem1 + p]);
            p++;
        }
    }

    for (int l = 0;l <8;l++) {
        printf("%d\n", arr[l]);
    }
}

void swap(int *a, int *b) 
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

swap switch elements. Может кто-нибудь сказать мне, как я могу это исправить?

спасибо:)

Answer 1

эй, спасибо за совет, к сожалению, мы попросили написать код без добавления массива. Я буду очень рад, если вы поможете мне решить проблему, спасибо:)

Здесьответ без добавления дополнительного массива:

#include <stdio.h>
#define REMINDER 3

void swap(int *a, int *b) 
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}    

int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9,0};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    int idx=0;
    for (int r=0; r<REMINDER; r++) {
        for (int i=0; i<arr_size; i++) {
            if (arr[i]%REMINDER==r) {
                swap(&arr[idx++], &arr[i]);
            }
        }
    }

    for (int i=0; i<arr_size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Answer 2

эй, спасибо за совет, к сожалению, мы попросили написать код без добавления массива. Я буду очень рад, если вы поможете мне решить проблему, спасибо:)

Answer 3

Поскольку вы хотите, чтобы ваша функция выполнялась за O (n), вы не можете полностью отсортировать массив.Все, что вам нужно сделать, это положить все элементы в 3 ведра.Следующий алгоритм работает в 2 этапа.

//First we count the number of elements in each bucket 
int count[3] ={0, 0, 0};
for (int i = 0; i < NUM_ELEMENTS; i++) {
    count[arr[i]%3]++;
}

Теперь, когда у нас есть количество элементов, мы можем вычислить смещения для каждого сегмента и создать и вывести массив

int output[NUM_ELEMENTS]; // In place bucketing can also be done using swaps
count[2] = count[0] + count[1];
count[1] = count[0];
count[0] = 0;


for (int i = 0; i < NUM_ELEMENTS; i++) {
    output[count[arr[i]%3]] = arr[i];
    count[arr[i]%3]++;
}

// Finally print the array

for (int i = 0; i < NUM_ELEMENTS; i++) {
    printf("%d", output[i]);
}

Демо на Ideone

Answer 4

Вот 1-проходный Алгоритм голландского национального флага * Реализация 1002 * (благодаря @Virgile, который указал на алгоритм)

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// Dutch National Flag (see xlinux.nist.gov/dads/HTML/DutchNationalFlag.html)
void sort3dnf(int *a, size_t n) {
    int *bot = a;
    int *mid = a;
    int *top = a + n - 1;
    while (mid <= top) {
        switch (*mid % 3) {
            default: swap(bot++, mid++); break;
            case 1: mid++; break;
            case 2: swap(mid, top--); break;
        }
    }
}

См. ideone.com /6QXXCN

Answer 5

Вот решение, которое вы ищете, которое использует тот же массив:

#include <stdio.h>

#define REMINDER 3

void swap(int *a, int *b) 
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}    

int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9,0};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    int idx=0;
    for (int r=0; r<REMINDER; r++) {
        for (int i=0; i<arr_size; i++) {
            if (arr[i]%REMINDER==r) {
                swap(&arr[idx++], &arr[i]);
            }
        }
    }

    for (int i=0; i<arr_size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Вот еще одно решение, которое проще использовать другое место для хранения результата:

#include <stdio.h>

#define REMINDER 3
#define ARR_SIZE 10

int main()
{
    int arr[ARR_SIZE] = {1,2,3,4,5,6,7,8,9,0};
    int arr_sorted[ARR_SIZE];

    int idx=0;
    for (int r=0; r<REMINDER; r++) {
        for (int i=0; i<ARR_SIZE; i++) {
            if (arr[i]%REMINDER==r) {
                arr_sorted[idx++]=arr[i];
            }
        }
    }

    for (int i=0; i<ARR_SIZE; i++) {
        printf("%d ", arr_sorted[i]);
    }

    return 0;
}