A program sort array by remainder 3

Question

I was requested to write an effecient function with running time n which sort array by the remainder of 3 the program puts the elements which the remainder from dividing in 3 is 0 afterwards the elements that the remainder is 1 and afterwards 2 for example the array {7, 16, 3, 28, 12, 31, 14, 12} will be sortes that way {12, 3, 12, 28, 16, 31, 7, 14} so I tries to write an efficient function but it have not cover all cases and does not works for all arrays

    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, Can anyone tells me how can I fix that?

thanks:)

Answer 1

hey thanks for the advice sadly we had requested to write the code without any added array I will be very glad if you could help me to solve the issue thanks :)

Here is the answer without adding any extra array:

#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

hey thanks for the advice sadly we had requested to write the code without any added array I will be very glad if you could help me to solve the issue thanks :)

Answer 3

Here's a 1-pass in-place Dutch national flag algorithm implementation (thanks to @Virgile who pointed out the algorithm)

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;
        }
    }
}

See ideone.com/6QXXCN

Answer 4

Since you want your function to run in O(n) time, you cannot sort the array completely. All you need to do is put all the elements in 3 buckets. The following algorithm runs in 2 phases.

//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]++;
}

Now that we have the number of elements, we can calculate the offsets of each bucket and create and output array

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]);
}

Demo on Ideone

Answer 5

Here is the solution which you are looking for which uses the same array:

#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;
}

Here is a another solution which is just simpler by using other place to store the result:

#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;
}