Алгоритм сортировки Radix

Question

Мне дали некоторые алгоритмы для обратной инженерии. Алгоритм ниже - это сортировка radix, но я очень смущен тем, что на самом деле происходит в коде.

Я новичок в алгоритмах и не уверен, как код сортирует элементы в массиве. Я не уверен, какие биты имеют отношение к алгоритму и какова маска. Вот код:

ArrayList<Integer> array = CopyArray(a); 
    Integer[] zerobucket = new Integer[a.size()]; 
    Integer[] onebucket = new Integer[a.size()]; 
    int i, bit; 
    Integer element, mask; 

    for (bit=0; bit<8; ++bit) { 
     int zc = 0; 
     int oc = 0; 

     for(i=0; i<array.size(); ++i) { 
      element = array.get(i); 
      mask = 1 << bit; 
      if ((element & mask) == 0) { 
       zerobucket[zc++] = array.get(i); 
      } else { 
       onebucket[oc++] = array.get(i); 
      } 
     } 
     for(i=0; i<oc; ++i) array.set(i,onebucket[i]); 
     for(i=0; i<zc; ++i) array.set(i+oc,zerobucket[i]); 
    } 
    return(array); 

Answer 1

Алгоритмы, где вы должны начать изучать программирование!

Чтобы увидеть, что делает недокументированный фрагмент кода, вам может потребоваться использовать псевдоязык для перевода работы в английскую инструкцию математики.

Например, вы отмечаете, что этот фрагмент должен работать только для 8-битных чисел (внешний цикл на бит). Грубое описание состоит в том, что элементы массива «сортируются» на два ведра в зависимости от того, бит в позиции «бит» равен нулю или один - начиная с бит в значительном положении аренды. Исходный массив затем переупорядочивается с «единицами», идущими перед «нулями» .., которые должны упорядочить массив от наибольшего до наименьшего.

Вам будет хорошо подобраны алгоритмы сортировки оснований и начните с этого, а не начиная с кода.

Answer 2

A mask, или битмаска, используется для «выключения» каждого бита, кроме тех, которые разрешены «видимыми» через маску. 0 s отфильтровывают бит, который они AND ed с, 1 s разрешают бит. Общее применение состоит, чтобы изолировать часть байтового размера целочисленного типа данных:

00000000 11111111 00000000 00000000 
& // Boolean AND 
10010101 10010101 10010101 10010101 
yields 
00000000 10010101 00000000 00000000 

Answer 3

Ваш алгоритм работает на 8-битных чисел, и вы смотрите на один бит за один раз. Более понятным примером является следующее: использование десятичного числа вместо двоичного.

Sort on 1s: 771 721 822 955 405 5 925 825 777 28 829 
Sort on 10s: 405 5 721 822 925 825 28 829 955 771 777 
Sort on 100s: 5 28 405 721 771 777 822 825 829 925 955 

После того, как мы сортируем на средней цифре, заметить, что числа сортируются по последних двух цифр. После сортировки по самой значащей цифре цифры полностью отсортированы.

То же самое касается двоичных. Количество ведер, которые мы используем для сортировки, это ТАКЖЕ, как основание цифра, мы используем в качестве ключа сортировки в течение одного прохода ведра или подсчета сортировки. «Radix» является синонимом базы номера, отсюда и название «radix sort». В вашем примере, это число 2.

Answer 4

/*try this iterative method and 100% working*/ 
    #include<stdio.h> 
    #include<math.h> 
    int sort(); 
    int display(); 
    long int a[20],n; 
    int main(){ 
    int i; 
    printf("enter the size:"); 
    scanf("%d",&n); 
    printf("\nenter the array elements\n"); 
      for(i=0;i<n;i++){scanf("%d",&a[i]);} 
      sort(); 
    return 0; 
      } 

int sort() 
{ 
int p=0,rad[20],q,s=0,i=0; 
int k1,k2,t; 
while(p<=3) 
    { 
q=0; 
      while(q<=9) 
       { 
       i=0; 
      while(a[i]!='\0') 
       { 
       t=pow(10,(p+1)); 
       k1=a[i]%t; 
       k2=k1/pow(10,p); 

      if(k2==q) {rad[s]=a[i];s++;} 
      i++; 
       } 
     q++; 
       } 
s=0; 
printf("\n sort for %dth\n",p); 
for(i=0;i<n;i++){a[i]=rad[i];} 
printf("\n"); 
    display(); 
p++; 
     } 
return 0; 
     }  

int display(){ 
int i=0; 
while(a[i]!='\0') 
{ 
printf("%d\t",a[i]); 
i++; 
} 
return 0; 
       }