Radix Sort Base 16 (Hexadecimals)

Question

LSD 기수 정렬에서 다음 (16 진수)를 정렬하려고 할 때 10hr 이상을 소비했지만 아무런 도움이되지 않았습니다. 웹상의이 주제에 대한 자료는 거의 없습니다.

0 4c7f CD80의 41fc의 782c 8b74 7eb1 9a03 AA01 73f1

내가 마스크 각 16 진수 (4 비트)를 처리하는 비트 연산을 수행 할 필요가 알고 있지만, 아무런 생각이 없다 방법과 장소 .

내가 GeeksforGeeks

void rsort(int a[], int n) { 
    int max = getMax(a, n); 
    for (int exp = 1; max/exp > 0; exp *= 10) { 
     ccsort(a, n, exp); 
    } 
} 

int getMax(int a[], int n) { 
    int max = a[0]; 
    int i = 0; 
    for (i = 0; i < n; i++) { 
     if (a[i] > max) { 
      max = a[i]; 
     } 
    } 
    return max; 
} 

void ccsort(int a[], int n, int exp) { 

    int count[n]; 
    int output[n]; 
    int i = 0; 

    for (i = 0; i < n; i++) { 
     count[i] = 0; 
     output[i] = 0; 
    } 
    for (i = 0; i < n; i++) { 
     ++count[(a[i]/exp) % 10]; 
    } 
    for (i = 1; i <= n; i++) { 
     count[i] += count[i - 1]; 
    } 
    for (i = n - 1; i >= 0; i--) { 
     output[count[(a[i]/exp) % 10] - 1] = a[i]; 
     --count[(a[i]/exp) % 10]; 
    } 
    for (i = 0; i < n; i++) { 
     a[i] = output[i]; 
    } 
} 

에서 코드 (이해)을 사용하고 또한이 문제에 유래 모두 확인했지만, 그들 중 누구도 세부 사항을 포함하지 않습니다.

Answer 1

void int_radix_sort(void) { 
    int group; //because extracting 8 bits 
    int buckets = 1 << 8; //using size 256 
    int map[buckets]; 
    int mask = buckets - 1; 
    int i; 
    int cnt[buckets]; 
    int flag = NULL; 
    int partition; 
    int *src, *dst; 

    for (group = 0; group < 32; group += 8) { 
     // group = 8, number of bits we want per round, we want 4 rounds 
     // cnt 
     for (int i = 0; i < buckets; i++) { 
      cnt[i] = 0; 
     } 
     for (int j = 0; j < n; j++) { 
      i = (lst[j] >> group) & mask; 
      cnt[i]++; 
      tmp[j] = lst[j]; 
     } 

     //map 
     map[0] = 0; 
     for (int i = 1; i < buckets; i++) { 
      map[i] = map[i - 1] + cnt[i - 1]; 
     } 

     //move 
     for (int j = 0; j < n; j++) { 
      i = (tmp[j] >> group) & mask; 
      lst[map[i]] = tmp[j]; 
      map[i]++; 
     } 
    } 
} 

시간이 지나면 답을 찾았습니다. 나는 아직도이 코드/응답에서 무슨 일이 벌어지고 있는지 이해할 수 없다. 나는 개념을 감싸는 머리를 얻을 수 없다. 잘하면, 누군가 설명 할 수 있습니다.

Answer 2

기수 정렬을 구현하는 더 간단한 방법이 있습니다. 최대 값을 확인한 후, 16> = 최대 값의 최소 전력을 찾습니다. 이것은 루프에서 max >> = 4로 할 수 있습니다. x를 증가 시키면 max가 0이 될 때까지 x가 16보다 큰 x가 원래의 최대 값이됩니다. 예를 들어, 최대 0xffff는 4 기수 정렬 패스를 필요로하며, 최대 0xffffffff는 8 기수 정렬 패스를 취합니다.

값의 범위가 정수에 대해 사용 가능한 전체 범위를 취할 가능성이 가장 높으면 최대 값을 결정할 필요가 없으며 정수 크기에 기수 정렬을 기반으로합니다.

예제 코드는 개수가 인덱스로 변환되는 방식으로 배열을 역방향으로 스캔하는 기수 정렬을 보여줍니다. 대체 방법을 사용하여 개수를 인덱스로 변환하면이 문제를 피할 수 있습니다. 다음은 32 비트 부호없는 정수에 대한 기본 256 기수 정렬의 예입니다. count/index 행렬을 사용하여 배열의 읽기 패스 한 개와 4 개의 기수 정렬 패스 (정렬 된 데이터가 원래 배열로 되돌아 간다)가 뒤 따르는 모든 4 행 카운트가 생성됩니다. std :: swap은 C 프로그램의 경우 포인터를 인라인으로 교체하여 대체 할 수있는 포인터를 교체하는 C++ 함수입니다. t = a; a = b; b = t, 여기서 t는 유형 uint32_t * (ptr을 부호없는 32 비트 정수로)입니다. 기본 16 기수 정렬의 경우, 행렬 크기는 [8] [16]이됩니다. 기수 정렬의

// a is input array, b is working array 
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // count/index matrix 
size_t i,j,m,n; 
uint32_t u; 
    for(i = 0; i < count; i++){   // generate histograms 
     u = a[i]; 
     for(j = 0; j < 4; j++){ 
      mIndex[j][(size_t)(u & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    for(j = 0; j < 4; j++){    // convert to indices 
     m = 0; 
     for(i = 0; i < 256; i++){ 
      n = mIndex[j][i]; 
      mIndex[j][i] = m; 
      m += n; 
     }  
    } 
    for(j = 0; j < 4; j++){    // radix sort 
     for(i = 0; i < count; i++){  // sort by current lsb 
      u = a[i]; 
      m = (size_t)(u>>(j<<3))&0xff; 
      b[mIndex[j][m]++] = u; 
     } 
     std::swap(a, b);    // swap ptrs 
    } 
    return(a); 
} 

Answer 3

귀하의 구현은 약간 잘못 :

• 이 10 대신 n의 크기를 가져야한다 음수 기능 ccsort()에
• 배열 count[]을 처리 할 수 ​​없습니다. n이 10보다 작 으면 기능이 작동하지 않습니다.
• 누적 계산을위한 루프가 한 걸음 지나치게 멀리 이동합니다 (for (i = 1; i <= n; i++)). 다시 <= 연산자가 버그를 일으 킵니다.
• 16 진수로 정렬 하겠지만 코드는 10 진수를 사용합니다.

  void ccsort(int a[], int n, int exp) { 
  
      int count[10] = { 0 }; 
      int output[n]; 
      int i, last; 
  
      for (i = 0; i < n; i++) { 
       // compute the number of entries with any given digit at level exp 
       ++count[(a[i]/exp) % 10]; 
      } 
      for (i = last = 0; i < 10; i++) { 
       // update the counts to have the index of the place to dispatch the next 
       // number with a given digit at level exp 
       last += count[i]; 
       count[i] = last - count[i]; 
      } 
      for (i = 0; i < n; i++) { 
       // dispatch entries at the right index for its digit at level exp 
       output[count[(a[i]/exp) % 10]++] = a[i]; 
      } 
      for (i = 0; i < n; i++) { 
       // copy entries batch to original array 
       a[i] = output[i]; 
      } 
  } 
  
  int getMax(int a[], int n) { 
      // find the largest number in the array 
      int max = a[0]; 
      for (int i = 1; i < n; i++) { 
       if (a[i] > max) { 
        max = a[i]; 
       } 
      } 
      return max; 
  } 
  
  void rsort(int a[], int n) { 
      int max = getMax(a, n); 
      // for all digits required to express the maximum value 
      for (int exp = 1; max/exp > 0; exp *= 10) { 
       // sort the array on one digit at a time 
       ccsort(a, n, exp); 
      } 
  } 
  

  위의 버전 때문에 모든 부서 및 운영 모듈로 상당히 비효율적이다 : 여기

는 설명과 함께 (약간) 개선 된 버전입니다. 16 진수에 수행은 변화와 마스크로 수행 할 수 있습니다

void ccsort16(int a[], int n, int shift) { 

    int count[16] = { 0 }; 
    int output[n]; 
    int i, last; 

    for (i = 0; i < n; i++) { 
     ++count[(a[i] >> shift) & 15]; 
    } 
    for (i = last = 0; i < 16; i++) { 
     last += count[i]; 
     count[i] = last - count[i]; 
    } 
    for (i = 0; i < n; i++) { 
     output[count[(a[i] >> shift) & 15]++] = a[i]; 
    } 
    for (i = 0; i < n; i++) { 
     a[i] = output[i]; 
    } 
} 

void rsort16(int a[], int n) { 
    int max = a[0]; 
    for (int i = 1; i < n; i++) { 
     if (a[i] > max) { 
      max = a[i]; 
     } 
    } 
    for (int shift = 0; (max >> shift) > 0; shift += 4) { 
     ccsort16(a, n, shift); 
    } 
} 

는 256 개 항목의 count 배열 한 번에 한 바이트를 정렬 할 약 두 배 빠른 것이다. rcgldr의 대답에서 볼 수 있듯이 한 번에 모든 숫자에 대한 계산을 계산하는 것이 더 빠릅니다.

이 구현은 여전히 ​​음수를 처리 할 수 ​​없다는 점에 유의하십시오.

Answer 4

귀하의 의견을 봅니다. 음수는 목록이 루프, 플래그 및 스왑으로 정렬 된 후 정렬하기 쉽다고 생각합니다. wb 부호없는 부동 소수점? -

부동 소수점 처리에 관해서는 16시 2분에서 itproxti 11월 1일 '16 예 345.768는 숫자입니다, 그것은 즉 그것은 345768하게, 정수로 변환 할 필요가있는 방법이있을 수 있습니다, 나는 곱한 그것으로 1000. 오프셋과 마찬가지로 -ve 수를 + ve 도메인으로 이동하므로 1000, 10000 등을 곱하면 소수 자리가 모두 0 인 수로 플로트가 바뀝니다. 그런 다음 int 또는 long 형식 변환 할 수 있습니다. 그러나 큰 값을 사용하면 개혁 된 전체 숫자가 int 또는 long 범위 전체에서 조절되지 않을 수 있습니다.

곱하기 숫자는 오프셋과 마찬가지로 일정해야하므로 크기 간의 관계가 유지됩니다. 8 비트 또는 16 비트와 같은 2의 거듭 제곱을 사용하는 것이 좋으며 비트 시프트 연산자를 사용할 수 있습니다. 그러나 옵셋 계산에 시간이 걸리므로 배율 계산에 시간이 걸릴 것입니다. 전체 배열을 검색하여 최소 숫자를 계산하면 곱 해져서 모든 숫자가 소수로 0으로 바뀝니다.

이 계산은 빠르지 만 필요한 경우 계속 수행 할 수 있습니다.