trier le tableau dans l'ordre décroissant de fréquence d'apparition des éléments dans le C

J'ai trouvé un moyen élégant pour la réalisation de ce genre en place avec le pire des cas, la complexité si O(N²) et moyenne complexité de O(N. log(N)).

La méthode utilise les étapes suivantes:

• Trier le tableau par ordre croissant des valeurs. J'utilise qsort avec une simple comparaison de la fonction pour cela.
• Analyse du tableau pour la plus longue séquence de valeurs en double.
• Si cette séquence n'est pas au début, de décaler les valeurs en place et de créer la séquence au début.
• Répétez le processus de numérisation à partir de la fin de l'étape précédente jusqu'à ce qu'il n'y a plus aucune duplication des séquences.

Voici le code:

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

OriginalL'auteur chqrlie

1) Créer un BINAIRES de RECHERCHE ARBRES et lors de la création d'un TBS de maintenir le comte i,e fréquence de chaque entrée de l'élément dans le même BST. Cette étape peut prendre en O(nLogn) si une auto-équilibrage de la BST est utilisé.

2) Ne Afinde de la traversée de la STB et de stocker chaque élément et le nombre de chaque élément dans un tableau auxiliaire. Nous allons l'appeler l'auxiliaire tableau en tant que ‘[]’. Notez que chaque élément de ce tableau est l'élément et de la fréquence de la paire. Cette étape prend O(n) fois.

3) Tri ‘[]’ en fonction de la fréquence des éléments. Cette étape prend O(nLohn) si O(nLogn) algorithme de tri est utilisé.

4) de Parcourir à travers le tableau trié ‘[]’. Pour chaque élément x, de l'imprimer, ‘freq’ fois où ‘freq’ est la fréquence de x. Cette étape prend O(n) fois.

Globale de la complexité temporelle de l'algorithme peut être minimum en O(nLogn) si l'on utilise un O(nLogn) algorithme de tri et d'utiliser un auto-équilibrage de la BST avec O(Logn) opération d'insertion.

source

OriginalL'auteur Ali

#include<stdio.h>
#include<malloc.h>
int* freq_sort_array(int*,int);
int main()
{
int a[10]={7,0,0,5,0,0,0,0,0,0};     /*input array*/
int *b,i;
printf("Input Array\n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
b=freq_sort_array(a,10);
printf("\nOutput array\n");
for(i=0;i<10;i++)
printf("%d ",b[i]);
}
/*Function for sorting array based on frequency*/
int* freq_sort_array(int *a,int len)
{
int i,j,temp,count,k=0,s=0,t=0;
int *b=(int*)malloc(len*sizeof(int));
int *c=(int*)malloc(len*sizeof(int));
for(i=0;i<len;i++)
{
for(j=i+1;j<len;j++)
{
if(a[j]==a[i])
{
temp=a[j];
for(j;j>i+1;j--)
{
a[j]=a[j-1];
}
a[++i]=temp;
}
}
}
for(i=0;i<len;i++)
{
a[j]=a[i];
count=1;
if(i!=len-1)
{
while(a[++i]==a[j]&& i<len)
count++;
i=i-1;
}
b[k]=a[j];
c[k++]=count;
}
for(i=1;i<k;i++)
{
for(j=0;j<k-i;j++)
{
if(c[j]<c[j+1])
{
c[j]=c[j]+c[j+1]-(c[j+1]=c[j]);
b[j]=b[j]+b[j+1]-(b[j+1]=b[j]);
}
}
}
for(i=0;i<k;i++)
{
for(j=0;j<c[i];j++)
a[s++]=b[i];
}
return a;
}

OriginalL'auteur MOHAMMED A J