Need opinions to optimize my code for sorting and find minimum number of K occurences

Heroking18 0
Viewed 34
int temp = 0;
int counter;
int match = 0;

int FindDup(int array[], int K, int N)
{
    // Sorting the array from small big numbers.
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            if (array[i] > array[j])
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }

    // Find minimum number of K occurences
    for (int i = 0; i < N; i++)
    {
        counter = 0;
        for (int j = 0; j < N; j++)
        {
            if (array[i] == array[j]) // checks if array element is equal
            {
                counter++;
            }
        }
        if (counter == K)
        {
            match = array[i];
            return match;
        }
    }
    return -1;
}

Info about this function: This function is a mix of sorting and finding minimum occurrences of an array.

Problem: The function does work as intended but needs optimization from another user for further improvements of the code. It would be great seeing someones opinions of what would be better and what could be changed.

Input:

arraySize: 10

arrayElements: 2 4 6 7 3 4 5 6 3 6

numberOfOccurrences: 2

Output: 3

data-structures c algorithm
1 Answers

since the input is just integer array and there is ain't no difference between saying there is 2 and another 2 as they all the same , you could go up with a hashing techniques , there is a lot of hashing techniques out there , just for a little demonstration , assume that the range of the numbers entered is so small , like from 0 -> 45 and all is positive , then you can use hashing . but if there is negative numbers then you have to use other techniques , if the array is like 0 1 2 5 3000 then this will create array of size 3001 if you used direct hashing techniques , but to solve this problem , there is other hashing techniques that could help you.

for example , you could do something like this :

#include <stdio.h>
#include <stdlib.h>

int main() {
    int arr[8] = {1, 10, 5, 5, 10, 4, 8, 11};
    int max = arr[0];

    /*get the maximum element in the array*/
    for(int i = 1; i < 8; i++)
    {
        if(arr[i] > max)
            max = arr[i];
    }

    /*create another variable of size = (max of arr) + 1 and initialized with zeros*/
    int *hashTable = (int*) calloc((max + 1), sizeof(int));

    /*hashing all the elements*/
    for (int i = 0; i < 8; ++i) {
        hashTable[arr[i]]++;
    }

    /*printing the sorted array*/
    for (int i = 0; i < (max+1);) {
        if(hashTable[i] > 0)
        {
            printf("%d\t", i);
            hashTable[i]--;
        }
        else
        {
            i++;
        }
    }

    return 0;
}

and this is the output:

1       4       5       5       8       10      10      11

here , using hashing , you can know the number of occurrence of each element and sort the array in time complexity O(N) .

so simply , read about hashing techniques . that could help answering your question

abdo Salm0
Related