C语言 按C中元素出现频率的降序对数组进行排序

Sort the array in decreasing order of frequency of occurrence of elements in C

提问by Nit kt

Question is to sort the array according to the frequency of the elements. For example, if the input array is

问题是根据元素的频率对数组进行排序。例如，如果输入数组是

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

then modify the array to:

然后将数组修改为：

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

I wrote the code for this and it is working correctly, but it is using a lot of space and has very high complexity.

我为此编写了代码并且它工作正常，但它使用了大量空间并且具有非常高的复杂性。

I am not satisfied with this solution and the logic I applied for this. Can anyone help to optimize this code or provide a better logic?

我对这个解决方案和我申请的逻辑不满意。任何人都可以帮助优化此代码或提供更好的逻辑吗？

My Code is:

我的代码是：

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

回答by chqrlie

I have found an elegant way to perform this sort in place with a worst case complexity if O(N²)and average complexity of O(N.log(N)).

如果O(N ²)和O(N.log(N)) 的平均复杂度，我找到了一种优雅的方法来执行这种排序，最坏情况的复杂度。

The method uses the following steps:

该方法使用以下步骤：

• Sort the array by increasing order of values. I use qsortwith a simple comparison function for this.
• Scan the array for the longest sequence of duplicate values.
• If this sequence is not at the start, shift the values in place and create the sequence at the start.
• Repeat the scan process from the end of the previous step until there are no longer any duplicate sequences.

• 通过增加值的顺序对数组进行排序。qsort为此，我使用了一个简单的比较函数。
• 扫描数组中最长的重复值序列。
• 如果此序列不在开头，请将值移动到位并在开头创建序列。
• 从上一步结束重复扫描过程，直到不再有任何重复序列。

Here is the 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;
}

回答by Will Ness

Sort the array by value; RLE the result, turning each span of equals into a pair of the element and the span's length (you can use an auxiliary array to back the second component); sort the pairs in descending order by the second component; there's your result. All in O(n log n)time and O(n)additional space.

按值对数组进行排序；RLE 结果，将等于的每个跨度转换为一对元素和跨度的长度（您可以使用辅助数组来支持第二个组件）；按第二个组件降序对对进行排序；这就是你的结果。全部在O(n log n)时间和O(n)额外空间。

回答by chmike

Here is an implementation using qsortfor sorting the values to easily calculate frequencies, and to sort the resulting frequency table by decreasing frequency. When two values have the same frequency, we sort by increasing value.

这是一个实现，qsort用于对值进行排序以轻松计算频率，并通过降低频率对结果频率表进行排序。当两个值具有相同的频率时，我们按递增值排序。

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

int cmp_int(const void *p1, const void *p2) {
    return *(const int *)p1 - *(const int *)p2;
}

typedef struct {
    int val;
    int cnt;
} freq;

int cmp_freq(const void *p1, const void *p2) {
    const freq *pf1 = (const freq *)p1;
    const freq *pf2 = (const freq *)p2;
    if(pf1->cnt == pf2->cnt)
        return pf1->val - pf2->val;
    return pf2->cnt - pf1->cnt;
}

void frequencySort(int tbl[], int n) {
    // sort values in ascending order
    qsort(tbl, n, sizeof(int), cmp_int);

    // fill frequency table with frequencies
    int nFreq = 0;
    freq *freqTbl = malloc(n*sizeof(freq));
    int val = tbl[0];
    int cnt = 1;
    for(int i = 1; i < n; i++) {
        if(tbl[i] != val) {
            freqTbl[nFreq].cnt = cnt;
            freqTbl[nFreq].val = val;
            nFreq++;
            val = tbl[i];
            cnt = 1;
        } else {
            cnt++;
        }
    }
    freqTbl[nFreq].cnt = cnt;
    freqTbl[nFreq].val = val;
    nFreq++;

    // sort by frequencies
    qsort(freqTbl, nFreq, sizeof(freq), cmp_freq);    

    // refill tbl by frequencies
    int m = 0;
    for(int i = 0; i < nFreq; i++)
        for(int j = 0; j < freqTbl[i].cnt; j++)
            tbl[m++] = freqTbl[i].val;

    free(freqTbl);
}

int main(int argc, char *argv[])
{
    int n = argc > 1 ? atoi(argv[1]) : 200;
    int *tbl;
    if (n <= 0 || (tbl = malloc(n * sizeof(int))) == NULL)
        return 1;
    srand(time(NULL));
    for (int i = 0; i < n; i++)
        tbl[i] = abs(rand()) % 10;

    printf("[%d", tbl[0]);
    for (int i = 1; i < n; i++)
        printf(",%d", tbl[i]);
    printf("]\n");

    frequencySort(tbl, n);

    printf("[%d", tbl[0]);
    for (int i = 1; i < n; i++)
        printf(",%d", tbl[i]);
    printf("]\n");

    free(tbl);
    return 0;
}

回答by klutt

You could start with a modified version of bucket sort, but stop halfways, after creating the bucket list.

您可以从存储桶排序的修改版本开始，但在创建存储桶列表后中途停止。

I made this, inspired by bucket sort. It's weakest link is quick sort, but I it could be modified to use bucket sort. I estimate that the complexity for an array A with length n and maximum value m is O(m + n log n) and if modified with bucket sort instead of qsort it would drop to O(m+n)

我做了这个，灵感来自桶排序。它最薄弱的环节是快速排序，但我可以修改它以使用桶排序。我估计长度为 n 且最大值为 m 的数组 A 的复杂度为 O(m + n log n)，如果使用桶排序而不是 qsort 进行修改，它将下降到 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;
}

回答by SynAck

1. Create a BINARY SEARCH TREEand while creating BST maintain the count i,e frequency of each coming element in the same BST. This step may take O(nLogn) time if a self-balancing BST is used.
2. Do Inorder traversal of BST and store every element and count of each element in an auxiliary array. Let us call the auxiliary array as ‘count[]'. Note that every element of this array is element and frequency pair. This step takes O(n) time.
3. Sort ‘count[]' according to the frequency of the elements. This step takes O(nLogn) time if an O(nLogn) sorting algorithm is used.
4. Traverse through the sorted array ‘count[]'. For each element x, print it ‘freq' times where ‘freq' is frequency of x. This step takes O(n) time.

1. 创建一个二进制搜索树，并在创建 BST 时维护同一 BST 中每个即将到来的元素的计数频率。如果使用自平衡 BST，此步骤可能需要 O(nLogn) 时间。
2. 对 BST 进行中序遍历并将每个元素和每个元素的计数存储在一个辅助数组中。让我们将辅助数组称为“count[]”。请注意，此数组的每个元素都是元素和频率对。这一步需要 O(n) 时间。
3. 根据元素的频率对 'count[]' 进行排序。如果使用 O(nLogn) 排序算法，则此步骤需要 O(nLogn) 时间。
4. 遍历已排序的数组 'count[]'。对于每个元素 x，打印 'freq' 次，其中 'freq' 是 x 的频率。这一步需要 O(n) 时间。

The overall time complexity of the algorithm can be minimum O(nLogn) if we use an O(nLogn) sorting algorithm and use a self-balancing BST with O(Logn) insert operation.

如果我们使用 O(nLogn) 排序算法并使用具有 O(Logn) 插入操作的自平衡 BST，则该算法的整体时间复杂度可以是最小的 O(nLogn)。

Geeks for Geeks

极客的极客

回答by MOHAMMED A J

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