私のbabysort関数の最終的な内部ループをコーディングするには？

Question

私は昇順に値をソートする必要があり、重複があります。私は "howMany"で何をしているのかと思います。しかし、私はカウント[j]に値を割り当てる最終的なループをコーディングすることに固執しています。

void babySort(int nums[], int length){ 
    int counts[100]={0}; 
    for(int i=0;i<length;i++) 
     counts[nums[i]]++; 
    int j=0; 
    for(int index=0; index<100; index++){ 
     int howMany=counts[index]; 

     // need innerloop here that assigns values to counts[j] 
    } 
} 

Answer 1

まあ、単にループにhowMany回実行し、numsの値を上書きします。

int j = 0; 
for (int counter = 0; counter < howMany; ++counter) 
{ 
    nums[j++] = index; 
} 

ここで、値をcountsに再割り当てする理由を確認します。 countsにはすでに各番号の頻度がnumsに格納されています。

Answer 2

これは非常に効率的なアルゴリズムではありません。部分的には、値のいずれも99より大きいか0未満であると仮定しており、ソートする数値がそれほど多くない場合には処理時間が浪費するためです。あなたは、おそらくこの1のようなアルゴリズムを使用したほうが良いと思います：

void babySort(int nums[], int length) { 
    int i,j; 
    int Value; 

    for(i = 1; i < length; i++) { 
     Value = nums[i]; 
     for(j = i - 1; j >= 0 && nums[j] > Value; j--) { 
     nums[j + 1] = nums[j]; 
     } 
     nums[j + 1] = Value; 
    } 
} 

Answer 3

おそらくこれは何が必要です：

void babySort(int nums[], int length){ 
    int counts[100]={0}; 
    for(int i=0;i<length;i++) 
     counts[nums[i]]++; 

    int j=0; 
    for(int index=0; index<100; index++){ 
     for(; counts[index]>0; counts[index]--) 
      nums[j++]=index; 
    } 
} 

for(index)ループは可能index値をスキャンし、それが1のことを発見したとき入力nums[]に遭遇した場合、for(counts)ループは、累積されたcount[index]を0にカウントするだけで、その値で適切な数のnums[]アイテムをその値で満たします。変数jは入力項目を数えます。

Answer 4

int findMinUnique(int* originArray, int* sortedArray, int lastInsertedValue) 
{ 
    int tempInt = 0x7fffffff;//max possible int32 

    for(int i = 0; i < length; i++) 
    { 
    if(originArray[i] < tempInt && originArray > lastInsertedValue) 
    { 
     tempInt = originArray[i]; 
    } 
    } 
    return tempInt; 
} 
void babySort(int nums[], int length) 
{ 
    int insertedValues = 0, lastInserted = -1; 
    int* anotherArray = new int[length]; 
    //you have to allocate memory for an array, it may be of any length 
    while(insertedValues < length) 
    { 
    int temp = findMinUnique(nums, anotherArray, lastInserted); 
    for(int j = 0; j < length j++) 
    { 
     if(nums[j] = tempValue) 
     lastInserted = anotherArray[insertedValues++] = nums[j]; 
    } 
    } 
    //if you need nums to become sorted, copy anotherArray to nums 
    for(int k = 0; k < length; k++) 
    nums[k] = anotherArray[k]; 
    delete[] anotherArray; 
}