함수는 어떻게 작동합니까?

Question

다음 두 알고리즘이 어떻게 작동하는지 설명해 주시겠습니까?

: 우리는이를 얻을 수 (1, 편곡, n)의 함수 countSort를 호출 한 후

:

int countSort(int arr[], int n, int exp) 
{ 
    int output[n]; 
    int i, count[n] ; 
    for (int i=0; i < n; i++) 
     count[i] = 0; 
    for (i = 0; i < n; i++) 
     count[ (arr[i]/exp)%n ]++; 
    for (i = 1; i < n; i++) 
     count[i] += count[i - 1]; 
    for (i = n - 1; i >= 0; i--) 
    { 
     output[count[ (arr[i]/exp)%n] - 1] = arr[i]; 
     count[(arr[i]/exp)%n]--; 
    } 
    for (i = 0; i < n; i++) 
     arr[i] = output[i]; 
} 


void sort(int arr[], int n) 
{ 
    countSort(arr, n, 1); 
    countSort(arr, n, n); 
} 

나는이 배열에 알고리즘을 적용하고 싶어

이 for 루프에서 countSort (arr, n, n) 함수를 호출하면

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

출력이 [-1] = arr [4]가됩니다.

그러나 배열에는 이러한 위치가 없습니다 ...

내가 잘못 했나요?

EDIT [] 도착 배열을 고려 = {10, 6, 8, 2, 3}, 어레이 카운트가 다음 요소를 함유 할 것이다 :

이들 숫자 표현하는 일을 ? 어떻게 사용합니까?

Answer 1

계수 정렬은 매우 간단합니다 -의 당신이 범위 1..3에서 숫자가 포함 된 배열이 있다고 가정 해 봅시다 :
count[1] = 4
count[2] = 2
: 각 숫자 배열에서 발생 횟수를 셀 수
[3,1,2,3,1,1,3,1,2]

을 count[3] = 3

이제 정렬 된 배열에서
번호 1,363,210은 1 (count[1] + count[2]에서 count[1] + count[2] + count[3] - 1에) 위치에 6..8
번호 3 하였다 (count[1]에서 count[1] + count[2] - 1에) 위치에 4..5
번호 2 하였다 (0에서 count[1] - 1 행) 0..3 위치를 차지한다.

이제 모든 숫자의 최종 위치를 알았으므로 모든 숫자를 올바른 위치에 삽입 할 수 있습니다. 그것은 기본적으로 무엇입니까 countSort 기능 않습니다.

그러나 실생활에서는 입력 배열에 1..3의 숫자 만 들어 있지 않으므로 LSD (least significant digit)의 숫자를 먼저 정렬 한 다음 LSD-1 ...에서 가장 중요한 숫자로 정렬하는 것이 솔루션입니다 손가락.
범위 0..9 (소수점 숫자 시스템에서 한 자리 숫자 범위)에서 숫자를 정렬하여 더 큰 숫자를 정렬 할 수 있습니다.
다음 코드는 (arr[i]/exp)%n in countSort입니다.n은 숫자 시스템의 기본입니다. 따라서 십진수의 경우 n = 10 및 exp은 1으로 시작하고 연속되는 숫자를 얻기 위해 반복 할 때마다 기준으로 곱해야합니다.
x = 1234, (x/exp)%n = 2 : 우리는 오른쪽에서 세 번째 자리를 얻으려면 예를 들어
, 우리는 n = 10 및 exp = 10^2를 사용합니다.

이 알고리즘은 기수 정렬라고 위키 백과에 자세히 설명되어 있습니다 : http://en.wikipedia.org/wiki/Radix_sort

Answer 2

그것은 당신의 countSort 일상 불구하고 선택하고 당신이 정상에 비해하던 그냥 뭐 그것이 결정하기 위해 시도하는 시간이 조금 걸렸다 radix 정렬. 반복을 분할하는 일부 버전과 countSort 및 sort 함수를 사용하여 시도한 것으로 보이는 실제 정렬 루틴이 있습니다. 그러나, 운동을 마치고 나면, 정렬 루틴의 필요한 부분을 포함시키지 않았 음이 분명했습니다. 원래 코드에서 다양한 컴파일/선언 문제를 수정 한 후 다음은 간과 한 부분을 추가합니다.

countSort 함수에서 count 배열의 크기가 잘못되었습니다. base 크기 (이 경우 10) 여야합니다. (당신은 5이었습니다) 기능을 통해 exp과 base의 사용을 혼동했습니다. exp 변수의 범위는 10이며, modulo base 연산과 결합하면 배열의 각 요소 값과 위치를 얻을 수 있습니다. 대신 modulo n 명이 있습니다. 이 문제는 또한 루프 범위에 침투하여 정확한 루프 범위가 0 < base 인 0 < n을 반복하는 루프 인덱스가 여러 개있었습니다.

는 그런 다음 정렬을 수행하기 위해 배열 통해 한계 패스의 수를 사용하는 원래의 배열의 최대 값을 찾는 를 놓쳤다. 실제로 countSort에있는 모든 기존 루프는 바깥 쪽 루프 while (m/exp > 0)을 반복해야합니다. 마지막으로 배열 내의 각 요소에 정렬을 적용하는 데 필요한 외부 루프 내에서 exp의 증가분을 생략했습니다. 그냥 혼란 스러울 것 같아요.하지만 다른 곳에서 복사/붙여 넣기 만하는 것이 아니라 정렬 루틴을 다시 작성하려는 노력에 찬사를 보냅니다. (복사/붙여 넣기를했을 수도 있지만 추가 문제가있는 경우 ...)

이러한 문제가 해결 될 때마다 정렬 작업이 수행됩니다. 변화를 보면서 그것이 무엇을하는지 이해하십시오. radix sort/count sort은 distribution sorts이며 숫자를 어디에 사용하고 인덱스를 조작하여 값을 비교하는 것이 아니라이 유형의 정렬을 처음에는 이해하기가 어렵습니다. 궁금한 점이 있으면 알려주세요. 생략 된 커플을 추가하고 10을 기본으로 하드 코딩을 방지하기 위해 함수 전체에서 명명 규칙을 보존하려는 시도를했습니다.

#include <stdio.h> 

void prnarray (int *a, int sz); 

void countSort (int arr[], int n, int base) 
{ 
    int exp = 1; 
    int m = arr[0]; 
    int output[n]; 
    int count[base]; 
    int i; 

    for (i = 1; i < n; i++)     /* find the maximum value   */ 
     m = (arr[i] > m) ? arr[i] : m; 

    while (m/exp > 0) 
    { 
     for (i = 0; i < base; i++) 
      count[i] = 0;     /* zero bucket array (count)  */ 

     for (i = 0; i < n; i++) 
      count[ (arr[i]/exp) % base ]++; /* count keys to go in each bucket */ 

     for (i = 1; i < base; i++)   /* indexes after end of each bucket */ 
      count[i] += count[i - 1]; 

     for (i = n - 1; i >= 0; i--)  /* map bucket indexes to keys  */ 
     { 
      output[count[ (arr[i]/exp) % base] - 1] = arr[i]; 
      count[(arr[i]/exp)%n]--; 
     } 

     for (i = 0; i < n; i++)    /* fill array with sorted output */ 
      arr[i] = output[i]; 

     exp *= base;      /* inc exp for next group of keys */ 
    }  
} 

int main (void) { 

    int arr[] = { 10, 6, 8, 2, 3 }; 
    int n = 5; 
    int base = 10; 

    printf ("\n The original array is:\n\n"); 
    prnarray (arr, n); 

    countSort (arr, n, base); 

    printf ("\n The sorted array is\n\n"); 
    prnarray (arr, n); 

    printf ("\n"); 

    return 0; 
} 

void prnarray (int *a, int sz) 
{ 
    register int i; 
    printf (" ["); 
    for (i = 0; i < sz; i++) 
     printf (" %d", a[i]); 
    printf (" ]\n"); 
} 

출력 : 그래서 @clcto

$ ./bin/sort_count 

The original array is: 

    [ 10 6 8 2 3 ] 

The sorted array is 

    [ 2 3 6 8 10 ]