ordina la matrice in ordine decrescente di frequenza di occorrenza degli elementi in C

Question

Domanda è ordinare l'array in base alla frequenza di elementi. Ad esempio, se la matrice di ingresso è

{ 2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12 } 

quindi modificare l'array:

{ 3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5 } 

Ho scritto il codice per questo e funziona correttamente, ma si sta usando un sacco di spazio e ha altissima complessità.

Non sono soddisfatto di questa soluzione e della logica che ho applicato per questo. Se qualcuno aiuta a ottimizzare questo codice o fornire una logica migliore.

il mio codice è:

#define _CRT_SECURE_NO_WARNINGS // this line to work code in visual studio 
#include <stdio.h> 

int main() { 
    /* 
    * n = number of integer 
    * i = loop variable 
    * j = inner loop variable 
    * c = number of distinct input 
    * buf = temprary storage for input value 
    * k = possibility of frequency of any no. 
    */ 

    int n, i, j, c = 0, buf, k; 
    int b; //act as flag 
    int arr[100] = { 0 }; 
    int stack[200] = { 0 }; 
    int top = -1; 
    printf("Enter the size of array(integer between 1-100):"); 
    scanf("%d", &n); 
    n *= 2; 

    printf("----------Enter the elements in the array----------\n\n"); 

    for (i = 0; i < n; i += 2) { 
     b = 0; 
     printf("Enter the element:"); 
     scanf("%d", &buf); 
     for (j = 0; j <= i; j += 2) { 
      if (arr[j] == buf) { 
       arr[j + 1]++; 
       b = 1; 
      }  
     } 
     if (b == 0) { 
      c++; 
      arr[c * 2 - 2] = buf; 
      arr[c * 2 - 1]++; 
     } 
    } 

    for (i = 0; i < c * 2; i++) 
     printf("%d ", arr[i]); 

    //input done in form of (element,times of occurence i.e. frequency),to print array, write this outside of comment: 
    //for (i = 0; i < c * 2; i++) printf("%d ", arr[i]); 

    for (k = 1; k < n/2; k++) { //checking for possible frequencies 
     for (j = c * 2 - 1; j > 0; j -= 2) { 
      //locations(index) to check in array for frequency 
      //left to right, so with same frequency no.,which occurred first will push in last. 
      if (arr[j] == k) 
       stack[++top] = j; //pushing(index of frequency) into stack in increasing order of frequency  
     } 
    } 

    //to print stack, write this outside of comment: 
    //printf("\nstack\n"); 
    //for (i = top; i > -1; i--) printf("%d ",stack[i]); 

    //printing of elements in there decreasing order of frequency(pop from stack) 
    //we have to print element, number of times of its frequency 

    printf("\n\n----------Output array in sorted order of there frequency----------\n"); 
    for (top; top > -1; top--) {   
     for (j = arr[stack[top]]; j > 0; j--) 
      printf("%d ", arr[stack[top] - 1]); 
    } 
} 

Answer 1

ho trovato un modo elegante per eseguire questo tipo di posto con un caso peggiore complessità se O (N) e la complessità media di O (N .log (N)).

Il metodo utilizza le seguenti fasi:

• ordinare l'array per ordine di valori crescenti. Io uso qsort con una semplice funzione di confronto per questo.
• Analizza la matrice per la sequenza più lunga di valori duplicati.
• Se questa sequenza non è all'inizio, spostare i valori in posizione e creare la sequenza all'inizio.
• Ripetere il processo di scansione dalla fine del passaggio precedente fino a quando non vi sono più sequenze duplicate.

Ecco il codice:

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

int int_cmp(const void *p1, const void *p2) { 
    int i1 = *(const int *)p1; 
    int i2 = *(const int *)p2; 
    return (i1 > i2) - (i1 < i2); 
} 

void print_array(const char *msg, const int *a, int n) { 
    printf("%s: ", msg); 
    for (int i = 0; i < n; i++) 
     printf("%d%c", a[i], " \n"[i == n - 1]); 
} 

int main(int argc, char *argv[]) { 
    int N = argc > 1 ? atoi(argv[1]) : 200; 
    int *array; 

    if (N <= 0 || (array = calloc(N, sizeof(*array))) == NULL) 
     return 1; 

    srand(N); 
    for (int i = 0; i < N; i++) { 
     unsigned int x = rand(); 
     array[i] = x * x % 10; 
    } 

    print_array("unsorted", array, N); 
    qsort(array, N, sizeof(int), int_cmp); 
    print_array(" sorted", array, N); 
    /* sort by decrasing frequency (assuming N > 0) */ 
    for (int i = 0;;) { 
     /* find the most repeated sequence in [i..N-1] */ 
     int rep = array[i]; 
     int n = 1, j, k; 
     for (j = k = i + 1; j < N; j++) { 
      if (array[j] == array[j - n]) { 
       rep = array[j]; 
       k = j + 1; 
       n++; 
      } 
     } 
     if (n == 1) { 
      /* no more duplicates, f-sort completed */ 
      break; 
     } 
     i += n; 
     if (k > i) { 
      /* shift the repeated sequence in place */ 
      while (k-- > i) { 
       array[k] = array[k - n]; 
      } 
      while (n-- > 0) { 
       array[k--] = rep; 
      } 
     } 
    } 
    print_array("f-sorted", array, N); 
    free(array); 
    return 0; 
} 

Answer 2

Si potrebbe iniziare con una versione modificata di bucket sort, ma fermarsi halfways, dopo aver creato la lista secchio.

Ho fatto questo, ispirato al tipo di benna. Il link più debole è l'ordinamento rapido, ma potrebbe essere modificato per utilizzare il tipo di bucket. Ho stima che la complessità di una matrice A con lunghezza n ed il valore massimo m è O (m + n log n) e se modificato con secchio sorta invece di qsort esso scenderebbe a O (m + n)

typedef struct { 
    int bucket; 
    int index; 
} element; 

int compare(const void *a, const void *b) 
{ 
    element *A = (element *) a; 
    element *B = (element *) b; 
    return(A->bucket < B->bucket); 
} 

void sortByFreq(int * arr, int len) 
{ 
    int arrMax=findMax(arr, len); // O(len) 
    element x[arrMax+1]; 
    for(int i=0; i<=arrMax; i++) { // O(arrMax) 
     x[i].bucket=0; 
     x[i].index=i; 
    } 
    for(int i=0; i<len; i++) // O(len) 
     x[arr[i]].bucket++; 
    qsort(x, arrMax+1, sizeof(element), compare); //O(len*log(len)) 

    int k=0; 
    for(int i=0; i<=arrMax; i++) // O(arrMax + len) 
     for(int j=0; j<x[i].bucket; j++) 
      arr[k++]=x[i].index; 
}