다음은 정수 배열 또는 정수로 키가 지정된 구조에 사용하는 정렬 알고리즘입니다. 정수 범위가 입력 크기 순서일 때 특히 유용합니다.

주요 아이디어는 정수의 발생 빈도를 결정하고 이를 사용하여 정렬 순서를 결정하는 것입니다.

예: {1,3,1,2} 배열을 얻었다고 가정해 보겠습니다.

먼저 이 입력에 대한 정수 범위, 최대값과 최소값, 1과 3을 결정합니다.

다음으로 배열을 만들고 이를 counts 배열이라고 부릅니다. 이는 정수 범위 1의 크기이므로 이 경우에는 3(3-1 1)입니다.
입력 배열을 반복하여 적절한 항목의 개수를 늘립니다. 주어진 입력 값의 개수는 counts[value - min]에 배치됩니다. 주어진 입력에 대해 counts[0]은 값 1에 대한 개수를 유지합니다.

이 결과로 개수 배열이 생성됩니다: {2,1,1}

이제 기본적으로 counts[i] = counts[i-1] counts[i]인 누적 개수를 결정합니다.

누적 개수 배열은 다음과 같습니다. {2,3,4}

정렬된 입력에 대한 출력 배열을 생성합니다.

이제 입력을 역순으로 반복합니다.

각 단계에서 입력 배열 값의 누적 개수를 검색합니다. 값은 검색된 개수 - 1에 해당하는 출력 배열 인덱스에 배치됩니다. 그런 다음 누적 개수 값을 감소시킵니다.

첫 번째 단계에서는 값 2가 검색되고 누적 개수는 3입니다. 값은 출력의 인덱스 2(3-1)에 배치되어야 합니다.

다음 반복에서는 값이 1이고 누적 개수가 2입니다. 따라서 이 '1'은 출력의 인덱스 1(2-1)에 배치됩니다.

계속해서 값은 3이고 누적 개수는 4입니다. 출력의 인덱스 3에 배치합니다.

마지막으로 두 번째 값은 1이고 누적 개수는 1입니다(처음 볼 때 개수가 감소했기 때문에). 따라서 이 '1'은 출력의 인덱스 0에 배치됩니다.

, 역순으로 반복하여 동일한 요소의 순서를 유지하여 정렬을 '안정'하게 만드는 방법을 확인하세요.

결과로 정렬된 배열은 {1,1,2,3}
입니다.

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min 1)
    for _, v := range in {
        counts[v-min]  
    }
    // determine cumulative counts
    for i := 1; i 



더 효율적으로 만들 수 있나요? 아래에 의견과 제안을 남겨주세요.

감사해요!

이 게시물과 이 시리즈의 모든 게시물에 대한 코드는 여기에서 확인할 수 있습니다.