algorithm
비둘기 구멍 정렬
수색…
비둘기 구멍 기본 정보 정렬
Pigeonhole Sort 는 요소 수 (n)와 가능한 키 값 (N)의 수가 거의 같은 요소 목록을 정렬하는 데 적합한 정렬 알고리즘입니다. 그것은 O (n + Range) 시간이 필요합니다. 여기서 n은 입력 배열의 요소 수이고 'Range'는 배열의 가능한 값 수입니다.
Pigeonhole에 대한 작업 (의사 코드) 정렬 :
- 배열의 최소값과 최대 값을 찾습니다. 최소값과 최대 값을 각각 '최소'와 '최대'로합시다. 또한 'max-min-1'로 범위를 찾으십시오.
- 처음에는 비어있는 "pigeonholes"의 배열을 범위와 같은 크기로 설정하십시오.
- 배열의 각 요소를 방문한 다음 각 요소를 비둘기 구멍에 넣습니다. 요소 입력 [i]는 인덱스 입력 [i] - min의 구멍에 놓입니다.
- 비둘기 배열 전체에 루프를 순서대로 시작하고 비어 있지 않은 구멍의 요소를 원래 배열에 다시 넣습니다.
pigeonhole 정렬은 counting 정렬과 유사하므로 여기에서는 Pigeonhole Sort와 Counting 정렬을 비교합니다.
비둘기 구멍의 예 :
우주 보조 장치 : O(n)
시간 복잡도 : O(n + N)
C # 구현
public class PigeonholeSort
{
private static void SortPigeonhole(int[] input, int n)
{
int min = input[0], max = input[n];
for (int i = 1; i < n; i++)
{
if (input[i] < min) min = input[i];
if (input[i] > max) max = input[i];
}
int range = max - min + 1;
int[] holes = new int[range];
for (int i = 0; i < n; i++)
{
holes[input[i] - min] = input[i];
}
int index = 0;
for (int i = 0; i < range; i++)
{
foreach (var value in holes)
{
input[index++] = value;
}
}
}
public static int[] Main(int[] input)
{
SortPigeonhole(input, input.Length);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow