Сортировка по убыванию

void radixSort(int *a, int arraySize){
vector<int> mybucket[10];
int i,j,maxVal = 0,digitPosition=1;
for(i = 0; i < arraySize; i++){
if(a[i] > maxVal)
maxVal = a[i];
}
int p =1;
char str[20];
sprintf( str,"%d",maxVal);
while( p <= strlen(str) ){
for(i = 0; i < arraySize; i++)
mybucket[(a[i]/digitPosition)%10].push_back(a[i]);
int k = 0;
for( i = 9;i>=0;i--){
for(j=0;j<mybucket[i].size();j++){
a[k++] = mybucket[i][j];
}
mybucket[i].clear();
}
digitPosition *= 10;
p+=1;
}
}

Edit1:

Здесь у нас есть 10 векторов mybuckets, каждый из которых будет содержать входные числа, основанные на их младшей значащей цифре K в десятичной форме. Где k будет варьироваться от 1 до N (максимальное количество цифр в заданном входе).

e.g.
for k =  2
and a = [1,23,45,127,345,1]
mybucket[0] = [1,1]
mybucket[2] = [23,127]
mybucket[4] = [45,345]

То, что делает приведенный выше код, это то, что он извлекает K-ю наименее значимую цифру из входных данных и помещает их в соответствующий сегмент на каждой итерации. После обработки всех чисел мы вынимаем эти числа из mybuckets и помещаем обратно во входной массив и запускаем процесс с (K + 1) -й младшей цифрой. Мы продолжаем делать это до тех пор, пока в заданных входных числах не останется ни одной младшей значащей цифры.

Примечание. Этот процесс будет выполняться в течение максимального количества разрядов в заданных числах ввода.

e.g. a = [83,86,77,15,93,35,86,92,49,21,62,27,90,59,63,26,40,26,72,36,93]
Iteration1
Bucket9[49,59,]
Bucket8[]
Bucket7[77,27,]
Bucket6[86,86,26,26,36,]
Bucket5[15,35,]
Bucket4[]
Bucket3[83,93,63,]
Bucket2[92,62,72,]
Bucket1[21,]
Bucket0[90,40,]

Iteration2
Bucket9[93,92,90,]
Bucket8[86,86,83,]
Bucket7[77,72,]
Bucket6[63,62,]
Bucket5[59,]
Bucket4[49,40,]
Bucket3[36,35,]
Bucket2[27,26,26,21,]
Bucket1[15,]
Bucket0[]
O/P:
[93,92,90,86,86,83,77,72,63,62,59,49,40,36,35,27,26,26,21,15]

Поскольку у нас максимальное количество цифр равно 2, то этот прогон за 2 итерации.

Проверьте Radix сортировка по убыванию для рабочего кода.

Edit2 / 3:
Вы можете использовать любую структуру данных, единственное, что нам нужно, это вставка в соответствующую корзину и извлечение из корзины. Здесь мы должны следовать строгому правилу для вставки и удаления в корзине, в противном случае вы можете получить o / p в случайном порядке.

Algorithm: (Assuming only positive number(s) is/are as given input)
k <- 1
maxVal <- 0
foreach number from inputs:
maxVal = max( number ,  maxVal )

/*Collection of bucket, which will hold all
the numbers whose kth significant digit is d[0-9].*/
buckets[ ]
1. foreach number from inputs:
d <- k_th_least_significant( number,  k )
buckets[ d ] .insert ( number )
2.  count <- 1
for indx = maximum bucket index to lowest bucket index:
for j = 1 to j <= buckets[ indx ].size():
inputs[ count ] = buckets[ indx ][ j ]
count <- count + 1
3. k <- k + 1
4. if number_of_digit( maxVal ) <= k :
go to step 1
5. Print inputs

Другой способ реализовать это.

1. Связанный список
   а) 2-мерный связанный список
   б) массив 1-мерного связанного списка

2. массив
   а) Массив динамического размера 1-D массив
   б) 2-D динамический массив здесь (мы имеем дело с изменением размера массива)
   c) Используйте массив максимального размера (1-D или 2-D)
   г) массив из стандартной библиотеки

3. сопоставить с STL или реализовать свой собственный. Использовать [0-9] в качестве ключа и значение в качестве
   а) связанный список
   б) указатель вектора или массива (возможно, вам придется иметь дело со вставкой)

4. Хеширование с использованием концепции сегмента (где ключ будет целым числом [0-9], и вы должны отобразить несколько значений в один и тот же ключ хеша)

5. Очередь (2-я очередь или 1-я очередь)

так далее.