비둘기홀 정렬

Pigeonhole sort
비둘기홀 정렬
클래스정렬 알고리즘
데이터 구조배열
최악의 경우 공연( + ) 여기서 N은 키 값의 범위이고 n은 입력 크기입니다.
최악의 경우 공간 복잡성

비둘기 구멍 정렬은 요소 수(n)와 가능한 키 값 범위(N)의 길이가 거의 동일한 요소 리스트를 정렬하는 데 적합한 정렬 알고리즘이다.[1]O(n + N) 시간이 필요하다.그것은 계수 분류와 유사하지만, "버킷 배열로 한 번, 그리고 다시 최종 목적지[whereas] 계수 분류는 보조 배열을 만든 다음 배열을 사용하여 각 항목의 최종 목적지를 계산하고 그 곳으로 항목을 이동시킨다"[2]는 점에서 다르다.

비둘기 구멍 알고리즘은 다음과 같이 작동한다.

  1. 정렬할 값의 배열이 주어진 경우 원래 배열의 키 범위에 있는 각 키에 대해 하나의 비둘기 구멍인 처음에 비어 있는 "피건홀"의 보조 배열을 설정하십시오.
  2. 원래 배열을 넘어가면서 각 값을 키에 해당하는 비둘기 구멍에 넣으십시오. 그러면 각 비둘기 구멍에는 해당 키와 함께 모든 값의 목록이 들어 있게 된다.
  3. 키를 증가시키는 순서로 비둘기 구멍 배열 위에 반복하고, 각각의 비둘기 구멍에 대해 요소들을 증가시키는 순서로 원래의 배열 안에 넣는다.

예

첫 번째 요소를 기준으로 값 쌍을 정렬했다고 가정해 보십시오.

  • (5, "안녕")
  • (3, "파이")
  • (8, "apple")
  • (5, "킹")

3에서 8 사이의 각 값에 대해 우리는 비둘기 구멍을 설정한 다음 각 원소를 비둘기 구멍으로 이동시킨다.

  • 3: (3, "파이")
  • 4:
  • 5: (5, "안녕"), (5, "킹")
  • 6:
  • 7:
  • 8: (8, "애플")

그런 다음 비둘기 구멍 배열을 순서대로 반복하고 원소를 원래 목록으로 다시 이동시킨다.

비둘기 구멍 정렬과 카운팅 정렬의 차이점은 카운트 정렬에서 보조 배열은 입력 요소 목록을 포함하지 않고 카운트만 포함한다는 것이다.

  • 3: 1
  • 4: 0
  • 5: 2
  • 6: 0
  • 7: 0
  • 8: 1

N이 n보다 훨씬 큰 어레이의 경우 버킷 정렬은 공간과 시간에 더 효율적인 일반화다.

파이썬 구현

로부터 타자 치기 수입하다 리스트, 투플레, 아무거나  반항하다 비둘기홀_공기(lst: 리스트[투플레[인트로, 아무거나]]) -> 없음:     """ in-place는 (키, 값) 튜플의 목록을 키별로 정렬한다.  :param lst: 튜플의 목록으로, 각 튜플에는 어떤 것이든 될 수 있는 숫자와 값이 있다. :return: 없음 """      밑의 = 분(핵심을 을 위해 핵심을, 가치를 매기다 에 lst)     사이즈를 맞추다 = 맥스.(핵심을 을 위해 핵심을, 가치를 매기다 에 lst) - 밑의 + 1      # 채울 빈 목록(목록) 만들기     # 키가 두 번 나타날 수 있기 때문에 목록이다.     비둘기 구멍: 리스트[리스트[투플레[인트로, 아무거나]]] = [[] 을 위해 _ 에 범위(사이즈를 맞추다)]      을 위해 핵심을, 가치를 매기다 에 lst:         색인을 달다 = 핵심을 - 밑의         비둘기 구멍 = 비둘기 구멍[색인을 달다]         비둘기 구멍.덧셈을((핵심을, 가치를 매기다))      lst.분명한()  # 리스트 재초기화 : 비둘기구멍에서 다시 채울 예정      을 위해 비둘기 구멍 에 비둘기 구멍:         lst.연장하다(비둘기 구멍)

참고 항목

참조

  1. ^ "NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort".
  2. ^ Black, Paul E. "Dictionary of Algorithms and Data Structures". NIST. Retrieved 6 November 2015.