sắp xếp mảng theo thứ tự giảm tần suất xuất hiện của các phần tử trong C

Question

Câu hỏi là sắp xếp mảng theo tần số của các phần tử. Ví dụ, nếu mảng đầu vào là

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

sau đó sửa đổi mảng tới:

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

tôi đã viết mã cho điều này và nó đang làm việc một cách chính xác, nhưng nó được sử dụng rất nhiều không gian và có độ phức tạp rất cao.

Tôi không hài lòng với giải pháp này và logic mà tôi đã áp dụng cho điều này. Nếu có ai giúp tối ưu hóa mã này hoặc cung cấp logic tốt hơn.

Mã của tôi là:

#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

Tôi đã tìm thấy một cách thanh lịch để thực hiện loại này ở vị trí với một trường hợp phức tạp nhất nếu O (N) và độ phức tạp trung bình của O (N .log (N)).

Phương pháp này sử dụng các bước sau:

• Sắp xếp mảng bằng cách tăng thứ tự của các giá trị. Tôi sử dụng qsort với một hàm so sánh đơn giản cho việc này.
• Quét mảng để có chuỗi giá trị trùng lặp dài nhất.
• Nếu chuỗi này không ở lúc bắt đầu, hãy thay đổi giá trị tại chỗ và tạo chuỗi lúc bắt đầu.
• Lặp lại quy trình quét từ cuối bước trước cho đến khi không còn bất kỳ chuỗi trùng lặp nào nữa.

Đây là mã:

#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

Bạn có thể bắt đầu với một phiên bản sửa đổi của bucket sort, nhưng dừng halfways, sau khi tạo danh sách xô.

Tôi đã thực hiện việc này, lấy cảm hứng từ việc sắp xếp nhóm. Liên kết yếu nhất là sắp xếp nhanh, nhưng tôi có thể sửa đổi liên kết này để sử dụng sắp xếp nhóm. Tôi ước tính rằng sự phức tạp cho một mảng A với chiều dài n và giá trị tối đa m là O (m + n log n) và nếu sửa đổi với xô loại thay vì qsort nó sẽ giảm xuống 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; 
}