question sur le comptage sorte

Question

salut j'ai écrire le code suivant qui imprime des éléments dans l'ordre de tri qu'un seul gros problème est qu'il utilise deux choix supplémentaires ici est mon code

public class occurance{ 
public static final int n=5; 


public static void main(String[]args){ 
// n is maximum possible value what it should be in array suppose n=5 then array may be 

int a[]=new int[]{3,4,4,2,1,3,5};// as u see all elements are less or equal to n 
//create array a.length*n 

int b[]=new int[a.length*n]; 
int c[]=new int[b.length]; 
for (int i=0;i<b.length;i++){ 
    b[i]=0; 
    c[i]=0; 
} 

    for (int i=0;i<a.length;i++){ 

    if (b[a[i]]==1){ 
    c[a[i]]=1; 
} 
else{ 
b[a[i]]=1; 
} 
} 
for (int i=0;i<b.length;i++){ 
    if (b[i]==1) { 
    System.out.println(i); 
} 
    if (c[i]==1){ 
    System.out.println(i); 
} 
} 





} 
} 
// 
1 
2 
3 
3 
4 
4 
5 
1.i have two question what is complexity of this algorithm?i mean running time 
2. how put this elements into other array with sorted order? thanks 

Answer 1

L'algorithme - comme indiqué ci-dessus - pistes dans O (n), où n est la taille du tableau a.

Cependant, je doute même que cela fonctionne correctement. Donc, voici un pseudocode-implémentation du tri par comptage. Il prend un tableau a d'entiers et stocke les valeurs triées dans un tableau d'entiers b. et b doivent être de même longueur.

void countingSort(int[] a, int[] b){ 
// first of all: count occurences 
int[] occ = new int[a.length]; 
for (int i = 0; i<a.length; ++i){ 
    occ[i]=0; 
} 
for (int i = 0; i<a.length; ++i){ 
    occ[a[i]] = occ[a[i]] + 1; 
} 
// second: put the elements in order into b 
int s = 0; 
for (int i = 0; i<a.length; ++i){ 
    // how often did element i occur? 
    for (int j = 0; j<occ[i]; ++j){ 
    b[s] = i; 
    s = s + 1; 
    } 
} 
} 

J'espère que je n'ai rien fait de mal.