Java에서 카운팅 정렬 알고리즘 구현
게시 됨: 2023-01-30
카운팅 정렬 알고리즘이란?
small ranges of integers 에 효율적인 정렬 알고리즘인 카운팅 정렬입니다. 입력 배열에서 각 값의 발생 횟수를 계산한 다음 해당 정보를 사용하여 각 값을 출력 배열의 올바른 위치에 배치하는 방식으로 작동합니다.
이 알고리즘의 시간 복잡도는 O(n+k) 입니다. 여기서 n은 입력 배열의 크기이고 k는 정수 범위입니다.
CrunchifyCountingSortAlgo.java
다음은 Java에서 Counting Sort를 완벽하게 구현한 것입니다. 원하는 IDEA에 복사하고 실행하십시오.
패키지 crunchify.com.java.tutorials;
import java.util.Arrays;
/**
* @author Crunchify.com
* 프로그램: Java에서 카운팅 정렬 알고리즘을 구현하는 방법은 무엇입니까?
* 카운팅 정렬은 배열의 요소를 정렬하는 정렬 알고리즘입니다.
* 배열에서 각 고유 요소의 발생 수를 계산하여.
*/
공개 클래스 CrunchifyCountingSortAlgo {
공개 정적 무효 메인(문자열[] 인수) {
// 10개 요소의 정수 배열
int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};
crunchifyPrint("원본 배열: " + Arrays.toString(crunchifyArray));
crunchifyPrint("\n");
CrunchifyCountingSortAlgo crunchify = new CrunchifyCountingSortAlgo();
crunchify.crunchifyCountingSortAlgorithm(crunchifyArray);
crunchifyPrint("\n");
crunchifyPrint("Crunchify 계산 정렬 알고리즘의 결과: " + Arrays.toString(crunchifyArray));
}
개인 정적 무효 crunchifyPrint(문자열 s) {
System.out.println(s);
}
/**
* 작성자: App Shah (Crunchify.com)
*
* 계수 정렬 논리:
* 작은 범위의 정수에 효율적인 정렬 알고리즘인 카운팅 정렬을 구현한 것입니다.
* 입력 배열에서 각 값의 발생 횟수를 세는 방식으로 작동합니다.
* 그런 다음 해당 정보를 사용하여 각 값을 출력 배열의 올바른 위치에 배치합니다.
* 이 알고리즘의 시간복잡도는 O(n+k),
* 여기서 n은 입력 배열의 크기이고 k는 정수의 범위입니다.
*/
공개 정적 int[] crunchifyCountingSortAlgorithm(int[] crunchifyArray) {
// getAsInt(): 값이 있으면 값을 반환하고 그렇지 않으면 NoSuchElementException을 발생시킵니다.
int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
int[] crunchifyCount = 새로운 int[crunchifyMax + 1];
// crunchifyCount 입력 배열에서 각 값의 발생 횟수
for (int i = 0; i < crunchifyArray.length; i++) {
crunchifyCount[crunchifyArray[i]]++;
crunchifyPrint("crunchifyCount[" + crunchifyArray[i]에 1 추가
+ "], crunchifyCount 배열은 이제: " + Arrays.toString(crunchifyCount));
}
crunchifyPrint("\n");
정수 k = 0;
for (int i = 0; i <= crunchifyMax; i++) {
for (int j = 0; j < crunchifyCount[i]; j++) {
crunchifyArray[k++] = i;
crunchifyPrint("위치 " + (k - 1)에 " + i + " 추가
+ " 출력 배열에서 출력 배열은 이제 " + Arrays.toString(crunchifyArray));
}
}
crunchifyArray 반환;
}
}IntelliJ IDEA 또는 Eclipse IDE에서 Java 애플리케이션으로 위의 프로그램을 실행하면 아래와 같은 결과가 나타납니다.
IntelliJ IDEA 콘솔 결과
원래 배열: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3] crunchifyCount[9]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] crunchifyCount[3]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] crunchifyCount[6]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] crunchifyCount[6]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] crunchifyCount[1]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] crunchifyCount[12]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] crunchifyCount[32]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] crunchifyCount[29]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1] crunchifyCount[2]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 1, 1, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1] crunchifyCount[9]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 1, 1, 1, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1] crunchifyCount[3]에 1을 추가하면 crunchifyCount 배열은 이제 [0, 1, 1, 2, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1] 출력 배열의 위치 0에 1을 추가하면 출력 배열은 이제 [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]입니다. 출력 배열의 위치 1에 2를 추가하면 출력 배열은 이제 [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]입니다. 출력 배열의 위치 2에 3을 추가하면 출력 배열은 이제 [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3]입니다. 출력 배열의 위치 3에 3을 추가하면 출력 배열은 이제 [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3]입니다. 출력 배열의 위치 4에 6을 추가하면 출력 배열은 이제 [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3]입니다. 출력 배열의 위치 5에 6을 추가하면 출력 배열은 이제 [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3]입니다. 출력 배열의 위치 6에 9를 추가하면 출력 배열은 이제 [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3]입니다. 출력 배열의 위치 7에 9를 추가하면 출력 배열은 이제 [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3]입니다. 출력 배열의 위치 8에 12를 추가하면 출력 배열은 이제 [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3]입니다. 출력 배열의 위치 9에 29를 추가하면 출력 배열은 이제 [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3]입니다. 출력 배열의 위치 10에 32를 추가하면 출력 배열은 이제 [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]입니다. Crunchify 계산 정렬 알고리즘의 결과: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32] 종료 코드 0으로 프로세스가 완료되었습니다.
Counting Sort Algorithm Java 프로그램 위에서 실행되는 문제에 직면하면 알려주세요.
