Понимание алгоритма сортировки Radix

Question

Я пытаюсь понять, как работает этот алгоритм сортировки оснований. Я новичок в алгоритмах и битах, поэтому мне это не подходит. До сих пор я добавил эти комментарии в свой код, чтобы попытаться упростить его понимание. Я не уверен, правильно ли понял концепцию, поэтому, если кто-нибудь может увидеть какие-либо проблемы с моими комментариями/что-то, что я не понимаю правильно, пожалуйста, помогите мне :)

Также кто-нибудь сможет объяснить эту строку кода me: mask = 1 < < bit;

Мой комментировал код:

public static ArrayList<Integer> RadixSort(ArrayList<Integer> a) 
    //This method implements the radix sort algorithm, taking an integer array as an input 
    { 
     ArrayList<Integer> array = CopyArray(a); 
     //Created a new integer array called 'array' and set it to equal the array inputed to the method 
     //This was done by copying the array entered to the method through the CopyArray method, then setting the results of the method to the new empty array 

     Integer[] zerobucket = new Integer[a.size()]; 
     Integer[] onebucket = new Integer[a.size()]; 
     //Created two more integer arrays to act as buckets for the binary values 
     //'zerobucket' will hold array elements where the ith bit is equal to 0 
     //'onebucket' will hold array elements where the ith bit is equal to 1 

     int i, bit; 
     //Created two integer variables i & bit, these will be used within the for loops below 
     //Both i & bit will be incremented to run the radix sort for every bit of the binary value, for every element in the array 

     Integer element, mask; 
     //Created an integer object called element, this will be used to retrieve the ith element of the unsorted array 
     //Created an integer object called mask, this will be used to compare the bit values of each element 

     for(bit=0; bit<8; ++bit) 
     //Created a for loop to run for every bit of the binary value e.g.01000000 
     //Change from 8 to 32 for whole integers - will run 4 times slower 
     { 
      int zcount = 0; 
      int ocount = 0; 
      //Created two integer variables to allow the 'zerobucket' and 'onebucket' arrays to be increment within the for loop below 

      for(i=0; i<array.size(); ++i) 
      //Created a nested for loop to run for every element of the unsorted array 
      //This allows every bit for every binary value in the array 
      { 
       element = array.get(i); 
       //Set the variable 'element' to equal the ith element in the array 
       mask = 1 << bit; 

       if ((element & mask) == 0) 
       //If the selected bit of the binary value is equal to 0, run this code 
       { 
        zerobucket[zcount++] = array.get(i); 
        //Set the next element of the 'zerobucket' array to equal the ith element of the unsorted array 
       } 
       else 
       //Else if the selected but of the binary value is not equal to 0, run this code 
       { 
        onebucket[ocount++] = array.get(i); 
        //Set the next element of the 'onebucket' array to equal the ith element of the unsorted array 
       } 
      } 

      for(i=0; i<ocount; ++i) 
      //Created a for loop to run for every element within the 'onebucket' array 
      { 
       array.set(i,onebucket[i]); 
       //Appended the ith element of the 'onebucket' array to the ith position in the unsorted array 
      } 

      for(i=0; i<zcount; ++i) 
      //Created a for loop to run for every element within the 'zerobucket' array 
      { 
       array.set(i+ocount,zerobucket[i]); 
       //Appended the ith element of the 'zerobucket' array to the ith position in the unsorted array 
      } 
     } 
     return(array); 
     //Returned the sorted array to the method 
    } 

Я не писал этот код я дал ему попробовать понять

Answer 1

Я отвечу на ваши вопросы в обратном порядке ...

маска = 1 < < бит;

Благодаря правилам старшинства, вы могли бы написать это как

маска = (1 < < бит);

Это немного более очевидно. Возьмите целое число 1 (0x01), сдвиньте его влево по позиции бита и назначьте его для маскировки. Поэтому, если бит равен 2, маска равна 00000010 (пропускание начальных нулей). Если бит равен 4, маска - 00001000. И так далее.

Причиной маски является линией, которая следующим образом:

, если ((элемент & маска) == 0)

, которая предназначается, чтобы определить, является ли бит в качестве позиции бит - это 1 или ноль. Элемент ANDed с битовой маской будет либо нулевым, либо ненулевым, в зависимости от того, является ли бит в том же положении, что и 1 в битовой маске, равным 0 или ненулевым соответственно.

Теперь более сложный вопрос. Рассматриваемый алгоритм представляет собой сортировку по методу наименьших значащих бит, что означает сортировку радикса, в которой проходы по отсортированным значениям идут от наименее значимого (или в случае целых чисел программного обеспечения, справа налево).

Следующий псевдокод описывает код выше:

array = copy (a) 
for every bit position from 0 to radix // radix is 8 
    for each item in array 
     if bit at bit position in item is 0 
      put item in zeroes bucket 
     else 
      put item in ones bucket 
    array = ordered concatenation of ones bucket and zeroes bucket 
return array 

Так почему же это работает? Вы можете думать об этом как о итеративном взвешенном ранжировании элементов в массиве. Все остальные биты равны, элемент с 1 битом будет более крупным, чем элемент с 0 бит (ранжировать элементы). Каждый проход становится более важным для окончательной позиции (вес рейтинга). Последовательное применение этих двоичных сортировок приведет к тому, что элементы, которые чаще всего имеют 1, чаще всего помещаются в ведро 1. Каждый раз, когда элемент остается в ведре 1, когда другие элементы этого не делают, этот элемент улучшает его относительное положение в ведро 1 по сравнению с другими элементами, которые в будущих проходах могут также иметь значение 1.Последовательное присутствие в ведре 1 связано с постоянным улучшением положения, логическая крайность которого будет наибольшим значением в массиве.

Надеюсь, что это поможет.