계산 정렬 - 데이터 구조 및 알고리즘 자습서 - TECHCODEVIEW.COM

카운팅 정렬이란 무엇입니까?

계산 정렬 는 비비교 기반 입력 값의 범위가 제한되어 있을 때 잘 작동하는 정렬 알고리즘입니다. 정렬할 요소의 개수에 비해 입력값의 범위가 작은 경우 특히 효율적입니다. 기본 아이디어 뒤에 계산 정렬 계산하는 것이다 빈도 입력 배열의 각 개별 요소를 식별하고 해당 정보를 사용하여 요소를 올바른 정렬 위치에 배치합니다.

계산 정렬 알고리즘은 어떻게 작동하나요?

1 단계 :

알아보세요 최고 주어진 배열의 요소.

inputArray[]에서 최대 요소 찾기

2 단계:

초기화 개수배열[] 길이의 최대+1 모든 요소를 다음과 같이 0 . 이 배열은 입력 배열 요소의 발생을 저장하는 데 사용됩니다.

countArray[] 초기화

3단계:

에서 개수배열[] , 입력 배열의 각 고유 요소 수를 해당 인덱스에 저장합니다.
예를 들어: 요소수 2 입력 배열에는 2. 그러니 매장 2 색인에서 2 에서 개수배열[] . 마찬가지로, 요소의 개수 5 입력 배열에는 1 , 따라서 저장 1 색인에서 5 에서 개수배열[] .

countArray[]의 각 요소 수를 유지합니다.

4단계:

저장 누적 합계 또는 접두사 합계 의 요소 중 개수배열[] 함으로써 countArray[i] = countArray[i – 1] + countArray[i]. 이는 입력 배열의 요소를 출력 배열의 올바른 인덱스에 배치하는 데 도움이 됩니다.

countArray[]에 누적 합계를 저장합니다.

5단계:

입력 배열의 끝에서 반복하고 끝에서 입력 배열을 순회하면 동일한 요소의 순서가 유지되므로 결국 이 정렬 알고리즘이 만들어집니다. 안정적인 .

업데이트 outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .

또한, 업데이트 countArray[ 입력Array[i] ] = countArray[ 입력Array[i] ] – -.

6단계: i = 6인 경우 ,

마이크로서비스 튜토리얼

업데이트 출력Array[ countArray[ inputArray[6] ] – 1] = inputArray[6]
또한, 업데이트 countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

inputArray[6]를 OutputArray[]의 올바른 위치에 배치

7단계: i = 5인 경우 ,

업데이트 출력Array[ countArray[ inputArray[5] ] – 1] = inputArray[5]
또한, 업데이트 countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

inputArray[5]를 OutputArray[]의 올바른 위치에 배치

8단계: i = 4의 경우 ,

업데이트 출력Array[ countArray[ inputArray[4] ] – 1] = inputArray[4]
또한, 업데이트 countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

inputArray[4]를 OutputArray[]의 올바른 위치에 배치

9단계: i = 3인 경우 ,

업데이트 출력Array[ countArray[ inputArray[3] ] – 1] = inputArray[3]
또한, 업데이트 countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

inputArray[3]를 OutputArray[]의 올바른 위치에 배치

10단계: i = 2인 경우 ,

업데이트 outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
또한, 업데이트 countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

inputArray[2]를 OutputArray[]의 올바른 위치에 배치

11단계: i = 1의 경우 ,

업데이트 출력Array[ countArray[ inputArray[1] ] – 1] = inputArray[1]
또한, 업데이트 countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

inputArray[1]을 OutputArray[]의 올바른 위치에 배치

12단계: i = 0인 경우,

업데이트 출력Array[ countArray[ inputArray[0] ] – 1] = inputArray[0]
또한, 업데이트 countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

inputArray[0]를 OutputArray[]의 올바른 위치에 배치

계산 정렬 알고리즘:

보조 배열 선언 개수배열[] 크기의 최대(입력 배열[])+1 그리고 그것을 초기화 0 .
트래버스 배열 입력 배열[] 각 요소를 매핑하고 입력 배열[] 의 지표로 개수배열[] 배열, 즉 실행 countArray[inputArray[i]]++ ~을 위한 0 <= 나는 < N .
배열의 모든 인덱스에서 접두사 합계를 계산합니다. 입력 배열 [].
배열 만들기 출력 배열[] 크기의 N .
트래버스 배열 입력 배열[] 끝에서 업데이트 outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . 또한, 업데이트 countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

위의 알고리즘을 구현하면 다음과 같습니다.

자바

import> java.util.Arrays;> public> class> CountSort {> >public> static> int>[] countSort(>int>[] inputArray) {> >int> N = inputArray.length;> >int> M =>0>;> >for> (>int> i =>0>

; i   M = Math.max(M, inputArray[i]);  }  int[] countArray = new int[M + 1];  for (int i = 0; i   countArray[inputArray[i]]++;  }  for (int i = 1; i <= M; i++) {  countArray[i] += countArray[i - 1];  }  int[] outputArray = new int[N];  for (int i = N - 1; i>= 0; i--) { 출력Array[countArray[inputArray[i]] - 1] = inputArray[i];  countArray[inputArray[i]]--;  } 출력 배열을 반환합니다;  } 공개 정적 void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9};  int[] outputArray = countSort(inputArray);  for (int i = 0; i System.out.print(outputArray[i] + ' '); } } }>

씨#

using> System;> using> System.Collections.Generic;> class> GFG> {> >static> List<>int>>CountSort(목록<>int>>입력 배열)> >{> >int> N = inputArray.Count;> >// Finding the maximum element of the array inputArray[].> >int> M = 0;> >for> (>int>

i = 0; i   M = Math.Max(M, inputArray[i]);  // Initializing countArray[] with 0  List countArray = 새 목록 (새로운 정수[M + 1]);  // inputArray[]의 각 요소를 // countArray[] 배열의 인덱스로 매핑합니다. for (int i = 0; i countArray[inputArray[i]]++; // 배열 countArray의 모든 인덱스에서 // 접두사 합계를 계산합니다. [] for (int i = 1; i<= M; i++)  countArray[i] += countArray[i - 1];  // Creating outputArray[] from the countArray[] array  List outputArray = 새 목록 (새로운 정수[N]);  for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i];  countArray[inputArray[i]]--;  } 출력 배열을 반환합니다;  } // 드라이버 코드 static void Main() { // 입력 배열 목록 inputArray = 새 목록 {4, 3, 12, 1, 5, 5, 3, 9 };  // 출력 배열 목록 outputArray = CountSort(inputArray);  for (int i = 0; i Console.Write(outputArray[i] + ' '); Console.WriteLine(); } }>

자바스크립트

function> countSort(inputArray) {> >const N = inputArray.length;> >// Finding the maximum element of inputArray> >let M = 0;> >for>

(let i = 0; i   M = Math.max(M, inputArray[i]);  }  // Initializing countArray with 0  const countArray = new Array(M + 1).fill(0);  // Mapping each element of inputArray as an index of countArray  for (let i = 0; i   countArray[inputArray[i]]++;  }  // Calculating prefix sum at every index of countArray  for (let i = 1; i <= M; i++) {  countArray[i] += countArray[i - 1];  }  // Creating outputArray from countArray  const outputArray = new Array(N);  for (let i = N - 1; i>= 0; i--) { 출력Array[countArray[inputArray[i]] - 1] = inputArray[i];  countArray[inputArray[i]]--;  } 출력 배열을 반환합니다; } // 드라이버 코드 const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // 입력 배열 정렬 const outputArray = countSort(inputArray); // 정렬된 배열 인쇄 console.log(outputArray.join(' ')); //이 코드는 Utkarsh가 제공한 것입니다.>

리눅스 디렉토리 이름 변경

C++14

#include> using> namespace> std;> vector<>int>>countSort(벡터<>int>>& inputArray)> {> >int> N = inputArray.size();> >// Finding the maximum element of array inputArray[].> >int> M = 0;> >for> (>int>

i = 0; i   M = max(M, inputArray[i]);  // Initializing countArray[] with 0  vector countArray(M + 1, 0);  // inputArray[]의 각 요소를 // countArray[] 배열의 인덱스로 매핑합니다. for (int i = 0; i countArray[inputArray[i]]++; // 배열 countArray의 모든 인덱스에서 // 접두사 합계를 계산합니다. [] for (int i = 1; i<= M; i++)  countArray[i] += countArray[i - 1];  // Creating outputArray[] from countArray[] array  vector 출력배열(N);  for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i];  countArray[inputArray[i]]--;  } 출력 배열을 반환합니다; } // 드라이버 코드 int main() { // 입력 배열 벡터 inputArray = {4, 3, 12, 1, 5, 5, 3, 9 };  // 출력 배열 벡터 outputArray = countSort(inputArray);  for (int i = 0; 나는 계산합니다<< outputArray[i] << ' ';  return 0; }>

파이썬3

def> count_sort(input_array):> ># Finding the maximum element of input_array.> >M>=> max>(input_array)> ># Initializing count_array with 0> >count_array>=> [>0>]>*> (M>+> 1>)> ># Mapping each element of input_array as an index of count_array> >for> num>in> input_array:> >count_array[num]>+>=> 1> ># Calculating prefix sum at every index of count_array> >for> i>in> range>(>1>, M>+> 1>):> >count_array[i]>+>=> count_array[i>-> 1>]> ># Creating output_array from count_array> >output_array>=> [>0>]>*> len>(input_array)> >for> i>in> range>(>len>(input_array)>-> 1>,>->1>,>->1>):> >output_array[count_array[input_array[i]]>-> 1>]>=> input_array[i]> >count_array[input_array[i]]>->=> 1> >return> output_array> # Driver code> if> __name__>=>=> '__main__'>:> ># Input array> >input_array>=> [>4>,>3>,>12>,>1>,>5>,>5>,>3>,>9>]> ># Output array> >output_array>=> count_sort(input_array)> >for> num>in> output_array:> >print>(num, end>=>' '>)>

산출

1 3 3 4 5 5 9 12>

계산 정렬의 복잡성 분석:

시간 복잡도 : O(N+M), 여기서 N 그리고 중 크기는 입력 배열[] 그리고 개수배열[] 각기.
- 최악의 경우: O(N+M).
- 평균 사례: O(N+M).
- 최선의 경우: O(N+M).
보조 공간: O(N+M), 여기서 N 그리고 중 가 차지한 공간이다 출력 배열[] 그리고 개수배열[] 각기.

카운팅 정렬의 장점:

카운팅 정렬은 일반적으로 입력 범위가 입력 개수 순서인 경우 병합 정렬, 퀵 정렬과 같은 모든 비교 기반 정렬 알고리즘보다 빠르게 수행됩니다.
카운팅 정렬은 코딩하기 쉽습니다.
계산 정렬은 안정적인 알고리즘 .

계산 정렬의 단점:

계산 정렬은 소수 값에서는 작동하지 않습니다.
정렬할 값의 범위가 너무 크면 계산 정렬이 비효율적입니다.
계산 정렬은 내부 정렬 알고리즘은 배열 요소를 정렬하기 위해 추가 공간을 사용합니다.