프록시맵 정렬

프록시맵 정렬
	임의 번호 목록을 정렬하는 삽입 정렬 예제.
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연
베스트 케이스 공연
평균 공연
최악의 경우 공간 복잡성

원소들은 쓰레기통들 사이에 분포되어 있다.

모든 버킷을 채운 후 정렬하는 버킷 정렬과 달리 요소는 삽입될 때 정렬된다.

ProxymapSort 또는 Proxmap sort는 데이터 항목 또는 키의 배열을 다수의 "하위선"(버킷이라고 하는 유사한 종류)으로 분할하여 작동하는 정렬 알고리즘이다.이름은 K가 최종 정렬된 순서로 상주할 하위 배열의 시작을 나타내는 "근접 지도"를 계산하기 위한 약칭이다.삽입 정렬을 사용하여 키를 각 하위 배열로 배치한다.키가 하위 배열 사이에 "잘 분포"된 경우, 정렬은 선형 시간에 발생한다.계산 복잡도 추정에는 서브레이의 수와 사용되는 근접 매핑 기능인 "맵 키"가 포함된다.그것은 버킷과 라딕스의 일종이다.

ProxymapSort가 완료되면 Proxmap검색은 정렬된 배열의 $O(1)$ 를 O $O(1)$ ( $O(1)$ ) $O(1)$ {\ $displaystyle O$ (1 $)}$ 시간 $O(1)$ 내에 찾을 수 있다.

두 알고리즘 모두 1980년대 후반 교수에 의해 발명되었다.토마스 A.어바인 캘리포니아 대학의 스탠디쉬.

개요

기본전략

일반적으로: 어레이 A에 키가 n개 있는 경우:

각 어레이 항목에 맵 키 기능을 적용하여 대상 어레이 A2의 하위 어레이에 키를 매핑하십시오.
"히트 카운트" H의 배열을 사용하여 동일한 하위 어레이에 매핑할 키 수 결정
각 버킷이 "proxmaps"의 배열을 사용하여 대상 배열에서 각 하위 배열의 시작 위치를 결정하여 각 버킷이 매핑될 모든 키를 고정하기에 정확히 적절한 크기가 되도록 한다.
각 키에 대해 "로케이션" L의 배열을 사용하여 매핑할 하위 어레이를 계산하십시오.
각 키에 대해 위치를 찾아 A2의 셀에 배치한다. 키가 이미 그 위치에 있는 키와 충돌하는 경우 삽입은 키를 제자리에 정렬하고 이 키보다 큰 키를 오른쪽으로 하나씩 이동하여 이 키를 위한 공간을 만든다.서브어레이는 매핑된 모든 키를 담을 수 있을 만큼 충분히 크기 때문에, 그러한 이동은 결코 키를 다음의 서브어레이로 넘치게 하지 않을 것이다.

단순화된 버전: 키가 n개인 어레이 A가 지정됨

초기화:n 크기의 heatCount, proxyMap 및 A.length의 2개 어레이(위치 및 A2)를 생성 및 초기화하십시오.
파티션:신중하게 선택한 mapKey 함수를 사용하여 A의 키를 사용하여 A2를 하위 배열로 나누십시오.
분산: A를 읽고 각 키를 A2의 버킷에 떨어뜨리고 필요에 따라 정렬을 삽입하십시오.
수집:순서대로 하위선을 방문하여 모든 요소를 원래 배열로 다시 넣거나 A2를 사용하십시오.

참고: "키"는 키와 학생 ID 및 이름을 포함하는 학생 개체 배열과 같은 다른 데이터도 포함할 수 있다.이는 ProxyMapSort를 키 자체만이 아니라 객체 그룹을 구성하는데 적합하게 만든다.

예

전체 배열 고려:키가 n개인 A[0 ~ n-1]A의 지표가 되게 하라.A의 키를 같은 크기의 배열 A2로 정렬하십시오.

맵키 기능은 맵키(키) = 플로어(K)로 정의된다.

배열표
A1	6.7	5.9	8.4	1.2	7.3	3.7	11.5	1.1	4.8	0.4	10.5	6.1	1.8
H	1	3	0	1	1	1	2	1	1	0	1	1
P	0	1	-9	4	5	6	7	9	10	-9	11	12
L	7	6	10	1	9	4	12	1	5	0	11	7	1
A2.	0.4	1.1	1.2	1.8	3.7	4.8	5.9	6.1	6.7	7.3	8.4	10.5	11.5

가성음

// 적중 횟수 계산 을 위해 i = 0 로 11 // 여기서 11은 n {     H[i] = 0; } 을 위해 i = 0 로 12 // 여기서 12는 A.길이 {     양치류 = 맵키(A[i]);     H[양치류] = H[양치류] + 1; }  런닝토탈 = 0; // 프록시 맵 계산 – 각 하위 어레이의 시작 위치 을 위해 i = 0 로 11     만일 H[i] = 0         P[i] = -9;     다른         P[i] = 런닝토탈;         런닝토탈 = 런닝토탈 + H[i];  을 위해 i = 0 로 12 // 계산 위치 – 서브 어레이 – A의 각 항목이 배치될 A2     L[i] = P[맵키(A[i])];  을 위해 I = 0 로 12; // 항목 정렬     A2.[I] = <텅 빈>; 을 위해 i = 0 로 12 // 각 항목을 시작부터 하위 배열로 삽입하고 순서를 유지 {     출발하다 = L[i]; // 이 항목의 하위 어레이는 이 위치에서 시작됨     삽입 만든 = 거짓의;     을 위해 j = 출발하다 로 (<그 종지부를 찍다 의 A2. 이다 찾았다, 그리고 삽입 아닌 만든>)     {         만일 A2.[j] == <텅 빈> // 하위 어레이가 비어 있는 경우 하위 어레이의 첫 번째 위치에 항목을 놓으십시오.             A2.[j] = A[i];             삽입 만든 = 진실의;         다른 만일 A[i] < A2.[j] // 키는 A2[j]에 속함             인트로 종지부를 찍다 = j + 1; // 서브 어레이의 사용된 부분의 끝을 찾는다 – 여기서 첫 번째 <기호>는             하는 동안에 (A2.[종지부를 찍다] != <텅 빈>)                 종지부를 찍다++;             을 위해 k = 종지부를 찍다 -1 로 j // 더 큰 키를 오른쪽 1 셀로 이동                 A2.[k+1] = A2.[k];                 A2.[j] = A[i];             삽입 만든 = 진실의; // 새 키 추가     } }

여기서 A는 정렬할 배열이며 mapKey 함수는 사용할 하위선의 수를 결정한다.예를 들어, 바닥(K)은 단순히 A의 데이터에서 정수만큼 많은 하위선을 할당한다.키를 상수로 나누면 하위선의 수가 감소한다. 문자 A-Z를 0–25로 변환하거나 문자열을 정렬하기 위해 첫 문자(0–255)를 반환하는 등, A의 요소 범위를 하위선으로 변환하는 데 다른 기능을 사용할 수 있다.서브레이는 데이터가 들어올 때 정렬되며, 버킷 정렬에서 흔히 볼 수 있듯이 모든 데이터가 서브 어레이에 배치된 후에는 정렬되지 않는다.

프록시맵 검색

ProxymapSearch는 이전에 수행된 ProxymapSort에서 생성된 ProxyMap 어레이를 사용하여 정렬된 어레이 A2의 키를 일정한 시간에 찾는다.

기본전략

ProxymapSort, MapKey 기능 유지, P 및 A2 어레이를 사용하여 키 정렬
키를 검색하려면 키가 데이터 세트에 있는 경우 키가 포함된 하위 배열의 시작인 P[MapKey(k)]로 이동하십시오.
순차적으로 하위 어레이 검색, 키가 발견되면 해당 키(및 관련 정보)를 반환하고, 키보다 큰 값을 찾으면 키가 데이터 집합에 없는 경우
컴퓨팅 P[MapKey(k)]는 $O(1)$ ( 1 $O(1)$ ) ${\displaystyle$ O $(1)}$ 시간이 $O(1)$ 소요된다.정렬 중에 키를 잘 배포하는 맵 키를 사용한 경우, 각 하위 배열은 상수 c로 경계되므로 키를 찾거나 키가 없음을 알기 위해서는 최대 c 비교가 필요하다. 따라서 프록시맵검색은 $O(1)$ ( $O(1)$ ) ${\displaystyle$ O $(1)}.$ 최악의 $O(1)$ 맵 키를 사용한 경우 모든 키가 동일한 하위 어레이에 있으므로 프록시 맵이 최악의 경우 검색에는 $O(n)$ ( $O(n)$ $O(n)$ 비교가 $O(n)$ 필요하다.

가성음

함수 mapKey(키)가 반환 플로어(키)임

proxyMap ← 이전에 생성된 n 크기 A2 map 이전에 정렬된 크기 n 함수 프록시맵 검색(키) 배열은 i = proxyMap[mapKey(키)에서 길이(어레이)까지 - 1을 위한 것이다(정렬된 경우).key == key then return sortedArray[i]

분석

퍼포먼스

H, P, L 연산에는 모두 $O(n)$ ( $O(n)$ ) $O(n)$ 시간이 $O(n)$ 소요된다.각각은 각 배열 위치에서 일정한 시간을 소비하면서 배열을 통과하는 한 번의 통과로 계산된다.

최악의 경우:MapKey는 모든 항목을 하나의 하위 어레이에 배치하여 표준 삽입 정렬과 $O(n^{2})$ $O(n^{2})$ ) ${\displaystyle O(n^{2})$ 의 시간을 생성한다 $O(n^{2})$
모범 사례:MapKey는 삽입 정렬의 최상의 경우가 발생하는 순서대로 각 하위 어레이에 동일한 수의 항목을 제공한다.각 삽입 $O(c)$ 은 O $O(c)$ ( $O(c)$ ) ${\displaystyle$ O $(c)}$ 이고 $O(c)$ 하위선의 크기는 c이며, p * c = n이므로 삽입 단계는 O $O(n)$ )를 취하고, 따라서 ProxmapSort는 $O(n)$ (n ) $O(n)$ 이다 $O(n)$
평균 사례:각 서브 어레이는 최대 크기 c, 상수; 각 서브 어레이에 대한 삽입 정렬은 최악의 경우 O(c^2) - 상수. (c 항목이 버킷에 배치될 때까지 정렬되지 않기 때문에 실제 시간은 훨씬 더 좋을 수 있다.)총 시간은 버킷 수(n/c), O $O(c^{2})$ $O(c^{2})$ ) ${\displaystyle$ O $(c^{2})$ $O(c^{2})$ = $O(n)$ $O(n)$ $O(n)$ 입니다 $O(n)$

최악의 경우를 피하기 위해서는 좋은 맵키 기능을 갖추는 것이 필수적이다.우리는 데이터 분포에 대해 알아야 좋은 열쇠를 생각해 낼 수 있다.

최적화

시간 절약: 위의 코드에 있는 것처럼 다시 계산할 필요가 없도록 MapKey(i) 값을 저장하십시오.
공간 절약:프록시맵은 일단 프록시맵을 계산하면 적중 횟수가 필요하지 않기 때문에 hitCount 어레이에 저장할 수 있으며, A2 대신 A로 데이터를 다시 정렬할 수 있으며, 지금까지 A 값이 정렬되었는지, 그렇지 않은지 주의할 경우.

JavaScript 코드 구현:

배열.원형을 뜨다.프록시맵소트 = 기능을 하다() {//- 편집일자 : 2019/11/13 대만 --//   시합을 하다 출발하다 = 0;   시합을 하다 종지부를 찍다 = 이.길이;   시합을 하다 A2. = 새로운 배열(종지부를 찍다);   시합을 하다 맵키 = 새로운 배열(종지부를 찍다);   시합을 하다 히트카운트 = 새로운 배열(종지부를 찍다);      을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) { 히트카운트[i] = 0; }   시합을 하다 분 = 이[출발하다];   시합을 하다 맥스. = 이[출발하다];   을 위해 (시합을 하다 i = 출발하다+1; i < 종지부를 찍다; i++) {     만일 (이[i] < 분) { 분 = 이[i]; }     다른 {만일 (이[i] > 맥스.) { 맥스. = 이[i]; }}   }   //최적화 1.맵키[i] 저장   을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) {     맵키[i] = 수학.마루를 깔다(((이[i] - 분 ) / (맥스. - 분 )) * (종지부를 찍다 - 1));     히트카운트[맵키[i]]++;   }   //최적화 2.ProxyMaps는 hitCount에 저장되어 있다.   히트카운트[종지부를 찍다-1] = 종지부를 찍다 - 히트카운트[종지부를 찍다-1];   을 위해 (시합을 하다 i = 종지부를 찍다-1; i > 출발하다; i--){     히트카운트[i-1] = 히트카운트[i] - 히트카운트[i-1];   }   //A[i]=이[i]를 A2 올바른 위치에 삽입   시합을 하다 insertIndex = 0;   시합을 하다 삽입 시작 = 0;   을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) {     insertIndex = 히트카운트[맵키[i]];     삽입 시작 = insertIndex;     하는 동안에 (A2.[insertIndex] != 무효의) { insertIndex++; }     하는 동안에 (insertIndex > 삽입 시작 && 이[i] < A2.[insertIndex-1]) {       A2.[insertIndex] = A2.[insertIndex-1];       insertIndex--;     }     A2.[insertIndex] = 이[i];   }   을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) { 이[i] = A2.[i]; } };

다른 정렬 알고리즘과 비교

ProxmapSort는 비교 정렬이 아니기 때문에 Ω(n log n) 하한은 적용할 수 없다.^{[citation needed]}그것의 속도는 그것이 비교를 기반으로 하지 않고, 이진 검색 트리를 사용할 때 행해지는 것과 같이 따라야 하는 동적으로 할당된 개체와 포인터를 사용하는 대신 어레이를 사용했기 때문에 기인할 수 있다.

ProxymapSort를 사용하면 Proxymap을 사용할 수 있음검색. O(n) 빌드 시간에도 불구하고 ProxyMapSearch는 $O(1)$ ( 1 $O(1)$ ) $O(1)$ 평균 $O(1)$ 액세스 시간으로 이를 보완하여 대용량 데이터베이스에 매우 호소력이 있다.데이터를 자주 업데이트할 필요가 없는 경우, 액세스 시간이 이 기능을 다른 비비교 정렬 기반 정렬보다 더 유리하게 만들 수 있다.

ProxmapSort와 관련된 일반 버킷 정렬

ProxmapSort와 마찬가지로 버킷 정렬은 일반적으로 0과 일부 최대 키 또는 값 M 사이의 n개의 숫자 입력 목록에서 작동하며 값 범위를 각각 크기 M/n의 n개의 버킷으로 나눈다. 각 버킷을 삽입 정렬을 사용하여 정렬하면 ProxmapSort와 버킷 정렬이 예측된 선형 시간으로 실행되도록 표시할 수 있다.^[1]^{[original research?]}그러나 이러한 종류의 성능은 클러스터링(또는 키가 너무 많은 버킷 수가 너무 적음)과 함께 저하된다. 많은 값이 서로 근접하게 발생하면 모두 하나의 버킷에 속하게 되고 성능이 심각하게 저하된다.이러한 동작은 또한 ProxmapSort에 대해서도 적용된다. 버킷이 너무 크면 성능이 심각하게 저하된다.

참조

^ 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein.알고리즘 소개, Second Edition.MIT 프레스 앤 맥그로우 힐, 2001. ISBN 0-262-03293-7.제8.4절: 버킷 정렬, 페이지 174–177.

토마스 A.스탠디시.Java의 데이터 구조.애디슨 웨슬리 롱먼, 1998년ISBN 0-201-30564-X.섹션 10.6, 페이지 394–405.
Standish, T. A.; Jacobson, N. (2005). "Using $O (n)$ Proxmap Sort and $O (1)$ Proxmap Search to motivate CS2 students (Part I)". ACM SIGCSE Bulletin. 37 (4). doi:10.1145/1113847.1113874.
Standish, T. A.; Jacobson, N. (2006). "Using $O (n)$ Proxmap Sort and $O (1)$ Proxmap Search to motivate CS2 students, Part II". ACM SIGCSE Bulletin. 38 (2). doi:10.1145/1138403.1138427.
Norman Jacobson "ProxmapSort & Proxmap의 개요UC 어바인 주, 도날드 브렌 정보 및 컴퓨터 과학 학부 컴퓨터 과학 학과의 "검색".

외부 링크

[1] 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein.알고리즘 소개, Second Edition.MIT 프레스 앤 맥그로우 힐, 2001. ISBN 0-262-03293-7.제8.4절: 버킷 정렬, 페이지 174–177.

[1]

v t 정렬 알고리즘
이론	계산 복잡성 이론 빅 O 표기법 총순번 목록 배치 안정성 비교 정렬 적응 정렬 정렬 네트워크 정수 정렬 X + Y 정렬 트랜스디코토머스 모형 양자 분류
Exchange sort	버블 정렬 칵테일 셰이커 분류 홀수-짝수 정렬 콤 정렬 Gnome sort 비율 확장 정렬 퀵소트 슬로우토트 스투지 분류 보고소트
선택 정렬	선택 정렬 힙스포트 스무스소트 데카르트 트리 정렬 토너먼트 정렬 사이클 정렬 약한 heap 분류
삽입 정렬	삽입 정렬 조개류 스플레이소트 트리 정렬 라이브러리 정렬 인내 정렬
정렬 병합	병합 정렬 계단식 병합 정렬 병합 정렬 진동 다상 병합 정렬
분포 정렬	미국 국기 종류 비드 정렬 버킷 정렬 버스토트 카운팅 정렬 보간 정렬 비둘기홀 정렬 프록시맵 정렬 라딕스 분류 플래시소트
동시 정렬	비토닉 정렬기 배처 홀수-짝수 병합 쌍방향 정렬 네트워크 샘플포트
잡종류	병합 정렬 차단 커크패트릭-레이시 분류 팀소트 인트로소트 스프레스포트 병합 삽입 정렬
기타	위상 분류 위상전순서 팬케이크 분류 스파게티 종류

Search

프록시맵 정렬

네임스페이스

더

목차

개요

기본전략

예

가성음

프록시맵 검색

기본전략

가성음

분석

퍼포먼스

최적화

다른 정렬 알고리즘과 비교

ProxmapSort와 관련된 일반 버킷 정렬

참조

외부 링크