sortuj tablicę w kolejności malejącej częstości występowania elementów w C

Question

Pytanie dotyczy sortowania tablicy zgodnie z częstotliwością elementów. Na przykład, jeśli tablica wejście jest

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

następnie zmodyfikować tablicę:

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

pisałem kod to i działa poprawnie, ale jest przy użyciu dużo miejsca i ma bardzo wysoka złożoność.

Nie jestem usatysfakcjonowany tym rozwiązaniem i logiką, którą o to wnioskowałem. Jeśli ktoś pomoże zoptymalizować ten kod lub zapewnić lepszą logikę.

Mój kod to:

#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

Znalazłem elegancki sposób wykonywania tego rodzaju w miejscu o najgorszym przypadku złożoność jeśli O (N) i średnia złożoność O (n .log (N)).

Sposób wykorzystuje następujące etapy:

• sortowania tablicy przez malejące wartości. Używam qsort z prostą funkcją porównującą do tego.
• Skanuj tablicę dla najdłuższej sekwencji zduplikowanych wartości.
• Jeśli ta sekwencja nie jest na początku, przesuń wartości w miejscu i utwórz sekwencję na początku.
• Powtórz proces skanowania od końca poprzedniego kroku, aż przestaną być duplikowane sekwencje.

Oto kod:

#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

Można zacząć od zmodyfikowanej wersji bucket sort, ale zatrzymać halfways, po utworzeniu goni.

Zrobiłem to, inspirowane sortowaniem kubełków. Najsłabsze łącze to szybkie sortowanie, ale można go zmodyfikować, aby użyć sortowania wiadra. I oszacować, że złożoność dla macierzy A, o długości n i maksymalnej wartości m wynosi O (m + n log N), w przypadku zmian w wiadrze rodzaj zamiast qsort spadłaby do 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; 
}