보간 정렬

내부 보간 태그 정렬
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연
베스트 케이스 공연
평균 공연
최악의 경우 공간 복잡성

보간 태그 정렬
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연
베스트 케이스 공연
평균 공연
최악의 경우 공간 복잡성

보간 정렬
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연
베스트 케이스 공연
평균 공연
최악의 경우 공간 복잡성

보간 분류는 버킷 분류의 일종이다.보간 공식을 사용하여 버킷에 데이터를 할당한다.일반적인 보간 공식은 다음과 같다.

보간 = INT((Array[i] - min) / (max - min) * (ArraySize - 1)

알고리즘.

보간 정렬(또는 히스토그램 정렬)^[1]보간식을 이용해 데이터 분열을 분산시키고 정복하는 분류 알고리즘이다.보간 정렬은 버킷 정렬 알고리즘의 변형이기도 하다.^[2]보간 정렬 방법은 원래 숫자 열에 해당하는 레코드 버킷 길이의 배열을 사용한다.유지 보수 길이 어레이를 작동함으로써, 재귀 알고리즘이 메모리 스택화로 인해 $O(n^{2})$ $O(n^{2})$ 복잡성이 O $O(n^{2})$ ( $O(n^{2})$ 2 $O(n^{2})$ ) ${\디스플레이$ 스타일 $O(n^{2})$ 로 변경되는 것을 방지할 수 있다.길이 배열의 분할 기록은 2차 함수를 사용하여 배열의 메모리 공간을 동적으로 선언하고 삭제할 수 있다.재귀 프로그램을 제어하는 데 필요한 공간 복잡성은 $O(3n)$ ( $O(3n)$ $O(3n)$ ${\displaystyle O(3n$ 동적으로 할당된 메모리의 2차원 배열과 기록 길이의 배열을 포함한다.그러나 실행 복잡성은 $O(n+k)$ O $O(n+k)$ ( $O(n+k)$ + $O(n+k)$ $){\displaystyle O(n+k)}$ 의 효율적인 정렬 방법으로 유지될 수 있다 $O(n+k)$ ^[3] 동적으로 할당된 메모리 배열은 링크된 목록, 스택, 대기열, 연관 배열, 트리 구조 등으로 구현할 수 있다.JavaScript와 같은 어레이 객체가 적용된다.데이터 구조의 차이는 데이터 액세스 속도 및 정렬에 필요한 시간과 관련이 있다.정렬된 배열의 값이 산술 진행에 대해 균일하게 분포되어 있을 때 보간 정렬 $O(n)$ 의 선형 시간은 O $O(n)$ ( $O(n)$ ) ${\displaystyle$ O $(n)}$ 입니다 $O(n)$

보간 정렬 알고리즘

정렬되지 않은 버킷의 길이를 기록하도록 버킷 길이 배열을 설정하십시오.원래 배열 길이로 초기화하십시오.
[Main Sort] 버킷 길이 배열을 지우고 정렬하는 경우지워지지 않으면 [Divide function]을 실행한다.
[Divide function] 버킷 길이 배열 끝에서 버킷 길이를 팝업하여 실행하십시오.버킷에서 최대값과 최소값을 찾으십시오.최대값이 최소값과 같을 경우 분할을 중지하기 위해 정렬이 완료된다.
2차원 배열을 모두 빈 버킷으로 설정하십시오.보간 번호에 따라 버킷으로 나누십시오.
버킷으로 나눈 후 버킷 길이를 버킷 길이의 배열에 밀어 넣으십시오.그리고 비어 있지 않은 모든 버킷에서 항목을 하나씩 원래 배열로 다시 넣는다.
[Main Sort](메인 정렬)로 돌아가십시오.

히스토그램 정렬 알고리즘

NIST 정의:버킷 정렬 알고리즘의 효율적인 3-통과 개선.^[5]

첫 번째 패스는 보조 배열의 각 버킷에 대한 항목 수를 세고 실행 합계를 만들어 각 보조 항목이 이전 항목의 수입니다.
두 번째 패스는 각 품목을 해당 품목의 키에 대한 보조 입력에 따라 적절한 버킷에 넣는다.
마지막 패스는 각 양동이를 분류한다.

연습

보간 정렬 구현

JavaScript 코드:

배열.원형을 뜨다.보간소트 = 기능을 하다() {   시합을 하다 divideSize = 새로운 배열();   시합을 하다 종지부를 찍다 = 이.길이;   divideSize[0] = 종지부를 찍다;   하는 동안에 (divideSize.길이 > 0) { 나누다(이); }    // ArrayList에 기능 분할 반복   기능을 하다 나누다(A) {     시합을 하다 사이즈를 맞추다 = divideSize.펑펑 터지다();     시합을 하다 출발하다 = 종지부를 찍다 - 사이즈를 맞추다;     시합을 하다 분 = A[출발하다];     시합을 하다 맥스. = A[출발하다];     을 위해 (시합을 하다 i = 출발하다 + 1; i < 종지부를 찍다; i++) {       만일 (A[i] < 분) { 분 = A[i]; }       다른 { 만일 (A[i] > 맥스.) { 맥스. = A[i]; } }     }     만일 (분 == 맥스.) { 종지부를 찍다 = 종지부를 찍다 - 사이즈를 맞추다; }     다른 {       시합을 하다 p = 0;       시합을 하다 양동이로 만들다 = 새로운 배열(사이즈를 맞추다);       을 위해 (시합을 하다 i = 0; i < 사이즈를 맞추다; i++) { 양동이로 만들다[i] = 새로운 배열(); }       을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) {         p = 수학.마루를 깔다(((A[i] - 분 ) / (맥스. - 분 ) ) * (사이즈를 맞추다 - 1 ));         양동이로 만들다[p].밀다(A[i]);       }       을 위해 (시합을 하다 i = 0; i < 사이즈를 맞추다; i++) {         만일 (양동이로 만들다[i].길이 > 0) {           을 위해 (시합을 하다 j = 0; j < 양동이로 만들다[i].길이; j++) { A[출발하다++] = 양동이로 만들다[i][j]; }           divideSize.밀다(양동이로 만들다[i].길이);         }       }     }   } };

보간 정렬 재귀 방법

최악의 경우 공간 복잡성: $O(n^{2})$ ( n $O(n^{2})$ ) $O(n^{2})$

배열.원형을 뜨다.보간소트= 기능을 하다() {//--- 편집일자:2019/08/31 --//   시합을 하다 출발하다 = 0;   시합을 하다 사이즈를 맞추다 = 이.길이;   시합을 하다 분 = 이[0];   시합을 하다 맥스. = 이[0];    을 위해 (시합을 하다 i = 1; i < 사이즈를 맞추다; i++) {     만일 (이[i] < 분) { 분 = 이[i]; }     다른 {만일 (이[i] > 맥스.) { 맥스. = 이[i];} }   }   만일 (분 != 맥스.) {     시합을 하다 양동이로 만들다 = 새로운 배열(사이즈를 맞추다);     을 위해 (시합을 하다 i = 0; i < 사이즈를 맞추다; i++) { 양동이로 만들다[i] = 새로운 배열(); }     시합을 하다 보간술 = 0;     을 위해 (시합을 하다 i = 0; i < 사이즈를 맞추다; i++) {       보간술 = 수학.마루를 깔다(((이[i] - 분) / (맥스. - 분)) * (사이즈를 맞추다 - 1));       양동이로 만들다[보간술].밀다(이[i]);     }     을 위해 (시합을 하다 i = 0; i < 사이즈를 맞추다; i++) {       만일 (양동이로 만들다[i].길이 > 1) { 양동이로 만들다[i].보간소트(); } // 재귀       을 위해 (시합을 하다 j = 0; j < 양동이로 만들다[i].길이; j++) { 이[출발하다++] = 양동이로 만들다[i][j]; }     }   } };

히스토그램 정렬 구현

배열.원형을 뜨다.히스토그램 정렬 = 기능을 하다() {//--- 편집일자:2019/11/14 --//   시합을 하다 종지부를 찍다 = 이.길이;   시합을 하다 정렬 배열 = 새로운 배열(종지부를 찍다);   시합을 하다 보간술 = 새로운 배열(종지부를 찍다);   시합을 하다 히트카운트 = 새로운 배열(종지부를 찍다);   시합을 하다 divideSize = 새로운 배열();   divideSize[0] = 종지부를 찍다;   하는 동안에 (divideSize.길이 > 0) { 분배하다(이); }    // 배열로 기능 배포 반복   기능을 하다 분배하다(A) {     시합을 하다 사이즈를 맞추다 = divideSize.펑펑 터지다();     시합을 하다 출발하다 = 종지부를 찍다 - 사이즈를 맞추다;     시합을 하다 분 = A[출발하다];     시합을 하다 맥스. = A[출발하다];     을 위해 (시합을 하다 i = 출발하다 + 1; i < 종지부를 찍다; i++) {       만일 (A[i] < 분) { 분 = A[i]; }       다른 { 만일 (A[i] > 맥스.) { 맥스. = A[i]; } }     }     만일 (분 == 맥스.) { 종지부를 찍다 = 종지부를 찍다 - 사이즈를 맞추다; }     다른 {       을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) { 히트카운트[i] = 0; }       을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) {         보간술[i] = 출발하다 + 수학.마루를 깔다(((A[i] - 분 ) / (맥스. - 분 ) ) * (사이즈를 맞추다 - 1 ));         히트카운트[보간술[i]]++;       }       을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) {         만일 (히트카운트[i] > 0) { divideSize.밀다(히트카운트[i]); }       }       히트카운트[종지부를 찍다-1] = 종지부를 찍다 - 히트카운트[종지부를 찍다-1];       을 위해 (시합을 하다 i = 종지부를 찍다-1; i > 출발하다; i--) {         히트카운트[i-1] = 히트카운트[i] - 히트카운트[i-1];       }       을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) {         정렬 배열[히트카운트[보간술[i]]] = A[i];         히트카운트[보간술[i]]++;       }       을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) { A[i] = 정렬 배열[i]; }     }   } };

변종

보간 태그 정렬

보간 태그 정렬은 보간 정렬의 변형이다.버킷 정렬 및 분할 방법을 적용하면, 배열 데이터는 수학 보간식에 의해 제한된 수의 버킷으로 분산되고, 이후 정렬이 완료될 때까지 버킷은 원래의 처리 프로그램을 재귀적으로 반복한다.

보간 태그 정렬은 보간 정렬을 위한 재귀 정렬 방법이다.재귀로 인한 스택 오버플로를 방지하기 위해 메모리가 충돌한다.대신 부울 데이터 유형 태그 배열을 사용하여 재귀 함수를 작동하여 메모리를 해제하십시오.필요한 추가 메모리 공간은 $2n+(n)bits$ + $2n+(n)bits$ ( $2n+(n)bits$ ) $2n+(n)bits$ i $2n+(n)bits$ s $2n+(n)bits$ 에 가깝다 $2n+(n)bits$ 동적으로 할당된 메모리의 2차원 배열과 부울 데이터 유형 태그 어레이를 포함한다.스택, 큐, 연관 배열 및 트리 구조를 버킷으로 구현할 수 있다.

자바스크립트 배열 객체가 이 정렬 방식에 적합하기 때문에 데이터 구조의 차이는 데이터 액세스 속도 및 따라서 정렬에 필요한 시간과 관련이 있다.정렬할 배열의 값이 균등하게 분포할 때 선형 시간 evenly(n)이 사용된다.버킷 정렬 알고리즘은 정렬을 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ g $){\displaystyle$ O $(nlogn)}$ 의 하한으로 제한하지 않는다 $O(nlogn)$ 보간 태그 정렬 평균 성능 복잡도는 $O(n+k)$ + $){\displaystyle O(n+k)}$ 이다 $O(n+k)$

보간 태그 정렬 알고리즘

태그 배열을 원래 배열 크기와 동일하게 설정하고 잘못된 값으로 초기화하십시오.
[Main Sort] 원본 배열의 모든 버킷이 정렬되었는지 여부를 결정한다.정렬이 완료되지 않으면 [Divide function]이 실행된다.
[Divide function] 버킷에서 최대값과 최소값을 찾는다.최대값이 최소값과 같을 경우 정렬이 완료되고 분할이 중지된다.
2차원 배열을 모든 빈 버킷으로 설정하십시오.보간 번호에 따라 버킷으로 나누십시오.
버킷으로 나눈 후 태그 배열에서 버킷의 시작 위치를 True 값으로 표시하십시오.그리고 비어 있지 않은 모든 버킷에서 항목을 하나씩 원래 배열로 다시 넣는다.
[Main Sort](메인 정렬)로 돌아가십시오.

연습

JavaScript 코드:

배열.원형을 뜨다.인터폴라이온태그소트 = 기능을 하다() {// Wale Chen은 "Wikipedia CC BY-SA 3.0 라이센스"에 동의한다.서명일 : 2019-06-21 //   시합을 하다 종지부를 찍다 = 이.길이;    만일 (종지부를 찍다 > 1) {      시합을 하다 출발하다 = 0 ;      시합을 하다 태그 = 새로운 배열(종지부를 찍다);          // 알고리즘 단계-1     을 위해 (시합을 하다 i = 0; i < 종지부를 찍다; i++) { 태그[i] = 거짓의; }      나누다(이);    }    하는 동안에 (종지부를 찍다 > 1) {                     // 알고리즘 단계-2     하는 동안에 (태그[--출발하다] == 거짓의) { } // 다음 버킷의 시작 찾기     나누다(이);    }    기능을 하다 나누다(A) {        시합을 하다 분 = A[출발하다];      시합을 하다 맥스. = A[출발하다];     을 위해 (시합을 하다 i = 출발하다 + 1; i < 종지부를 찍다; i++) {        만일 (A[i] < 분) { 분 = A[i]; }        다른 { 만일 (A[i] > 맥스.) { 맥스. = A[i]; } } }     만일 ( 분 == 맥스.) { 종지부를 찍다 = 출발하다; }    // 알고리즘 단계 3 다음 버킷의 끝부분으로 시작     다른 {                                                 시합을 하다 보간술 = 0;        시합을 하다 사이즈를 맞추다 = 종지부를 찍다 - 출발하다;        시합을 하다 버킷 = 새로운 배열( 사이즈를 맞추다 );    // 알고리즘 단계-4       을 위해 (시합을 하다 i = 0; i < 사이즈를 맞추다; i++) { 버킷[i] = 새로운 배열(); }         을 위해 (시합을 하다 i = 출발하다; i < 종지부를 찍다; i++) {            보간술 = 수학.마루를 깔다 (((A[i] - 분) / (맥스. - 분)) * (사이즈를 맞추다 - 1));          버킷[보간술].밀다(A[i]);        }        을 위해 (시합을 하다 i = 0; i < 사이즈를 맞추다; i++) {         만일 (버킷[i].길이 > 0) {    // 알고리즘 단계-5           태그[출발하다] = 진실의;            을 위해 (시합을 하다 j = 0; j < 버킷[i].길이; j++) { A[출발하다++] = 버킷[i][j]; }          }        }       }   } // 알고리즘 단계-6 };

내부 보간 태그 정렬

내부 보간 태그 정렬은 보간 정렬의 내부 알고리즘이다.In-place Interpolation Tag Sort는 N번 비트 태그를 유지하여 스와핑 횟수 N번만으로 정렬할 수 있지만, 정렬할 배열은 연속 정수 시퀀스여야 하며 반복되지 않아야 하며, 또는 시리즈가 산술 진행 횟수에 대해 완전히 균등하게 분포되어 있어야 한다.

요인 열 데이터를 반복해서는 안 된다.예를 들어 0~100번 정렬은 한 번에 정렬할 수 있다.교환 횟수는 $O(n)$ ( $O(n)$ ) $O(n)$ 이고 $O(n)$ 계산 시간 $O(n)$ 는 $O(n)$ O ( $O(n)$ $O(n)$ {\ $displaystyle$ O( $n$ 이고, 최악의 공간 $O(n)bits$ 는 $O(n)bits$ O $O(n)bits$ ( $O(n)bits$ ) $O(n)bits$ $O(n)bits$ s $O(n)bits$ {\ $displaystyle$ O $(n)bits}$ 이다 $O(n)bits$ 시리즈의 특성이 이 분류법의 조건부 요구조건을 만족한다면: "배열은 연속형 인트이다.eger 또는 반복되지 않는 산술적 진행", 인플레이스 보간 태그 정렬은 매우 빠르고 메모리 공간을 절약하는 훌륭한 정렬 방법이 될 것이다.

내부 보간 태그 정렬 알고리즘

in-place Interpolation Tag Sort는 반복되지 않는 연속 정수 시리즈를 정렬하고, 원래 배열과 길이가 같은 부울 데이터 유형 태그 배열 하나만 정렬하며, 배열은 처음부터 데이터의 보간법을 계산하며, 보간법은 배열의 새 위치를 가리킨다.Position, 스와핑된 위치는 태그 배열의 해당 위치에서 true로 표시되며, 배열의 끝이 정렬될 때까지 증분된다.

알고리즘 프로세스:

초기화할 태그 배열의 개수를 false 값으로 설정하십시오.
태그가 거짓일 경우 배열을 방문하여 보간=p에 해당하는 위치를 계산하십시오.
a[i]와 a[p]를 교환하고 tag[p] = true로 한다.
둘러보기 배열이 완료되고 정렬이 완료된다.

연습

JavaScript 코드:

배열.원형을 뜨다.InPlaceTagSort = 기능을 하다() { // 날짜 편집: 2019-07-02   시합을 하다 n = 이.길이;   시합을 하다 태그 = 새로운 배열(n);   을 위해 (i = 0; i < n; i++) { 태그[i] = 거짓의; }   시합을 하다 분 = 이[0];   시합을 하다 맥스. = 이[0];   을 위해 (i = 1; i < n; i++) { 만일 (이[i] < 분) { 분 = 이[i]; }   다른 { 만일 (이[i] > 맥스.) { 맥스. = 이[i]; } } }    시합을 하다 p = 0;   시합을 하다 임시 변통하다 = 0;   을 위해 (i = 0; i < n; i++) {     하는 동안에 (태그[i] == 거짓의) {        p = 수학.마루를 깔다(((이[i] - 분) / (맥스. - 분)) * (n - 1));       임시 변통하다 = 이[i];       이[i] = 이[p];        이[p] = 임시 변통하다;       태그[p] = 진실의;      }    }  }; 니즈 소트어레이.InPlaceTagSort();

$O(n)$ ) $O(n)$ 시간에서 $O(n)$ 수행된 인플레이스 정렬의 원점

도날드 크누스는 '알고리즘의 수학적 분석'(정보처리 '71, North Holland Public'72)에서 "...복제적 복잡성에 대한 연구는 우리가 매일 직면하는 더 일상적인 문제에 대한 우리의 도구를 날카롭게 다듬는 흥미로운 방법"이라고 말했다.

미국의 유명한 컴퓨터 과학자 도널드 크누스는 알고리즘의 수학적 분석에서 다음과 같이 지적했다.정렬 문제와 관련하여 크누스는 효과적인 현장 순열은 본질적으로 사이클 리더를 찾는 문제와 연관되어 있으며, 우리가 퍼뮤의 양을 지정하는 n개의 추가 "태그" 비트를 조작할 수 있다면 현장 순열은 $O(n)$ ( $O(n)$ ) $O(n)$ 번으로 $O(n)$ 쉽게 수행될 수 있다고 지적한다.Tation은 어느때나 수행되었다.이러한 태그 비트가 없으면 "모든 알고리즘이 평균적으로 $O(nlogn)$ O $O(nlogn)$ ( $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ n $){\displaystyle$ O $(nlogn)}$ 단계에서 $O(nlogn)$ 현장 순열화를 요구할 것으로 추측하는 것이 타당해 보인다"고 결론짓는다." ^[6]

In-place Interpolation Tag Sort는 도날드 크누스 교수가 말한 정렬 알고리즘 중 하나이다. "n개의 추가 "태그" 비트를 조작한다...사이클 리더를 찾고 현장 순열은 O $O(n)$ ( $O(n)$ ) ${\displaystyle$ O $(n)}$ 번으로 $O(n)$ 쉽게 수행할 수 있다."

유사분류법

다른 정렬 방법과 재귀 알고리즘을 혼합하는 버킷 정렬

버킷 정렬을 다른 정렬 방법과 혼합하여 정렬을 완료할 수 있다.버킷 정렬과 삽입 정렬을 기준으로 정렬할 경우, 또한 상당히 효율적인 정렬 방법이다.그러나 영상 시리즈가 값에서 큰 편차를 보이는 경우:예를 들어, 시리즈의 최대값이 N 곱하기보다 클 경우 다음으로 가장 큰 값이다.일련의 열이 처리된 후에는 최대값을 제외한 모든 요소가 동일한 버킷에 포함되는 분포가 된다.두 번째 정렬 방법은 삽입 정렬을 사용한다.실행 복잡성이 $O(n^{2})$ 2 $O(n^{2})$ ) ${\displaystyle O(n^{2})$ 로 떨어질 수 있음 $O(n^{2})$ 이는 버킷 소트 사용의 의미와 고속 성능을 상실했다.

보간 정렬은 버킷 정렬을 재귀적으로 사용하는 방법이다.재귀 작업을 수행한 후에도 버킷 정렬을 사용하여 시리즈를 분산시키십시오.이것은 위의 상황을 피할 수 있다.재귀 보간 정렬 실행 복잡성을 $O(n^{2})$ $O(n^{2})$ ) $O(n^{2})$ 로 만들려면 전체 시리즈에 요인 증폭을 표시해야 한다 $O(n^{2})$ 사실, 일련의 특별한 분포가 일어날 가능성은 거의 없다.

참조

^ NIST Algorithm. "interpolation sort". Definition: See histogram sort.
^ "Histogram sort". Another variant of bucket sort known as histogram sort or counting sort adds an initial pass that counts the number of elements that will fall into each bucket using a count array. Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, leaving no space overhead for bucket storage.^{[별도 참조]}
^ ^a ^b "桶排序（Bucket sort）" (in Chinese). 平均時間複雜度（Average performance） $O(n+k)$ ^{[별도 참조]}
^ "Bucket sort Average-case analysis". en.wikipedia. Note that if k is chosen to be $k=n$ , then bucket sort runs in $O(n)$ average time, given a uniformly distributed input.^{[별도 참조]}
^ NIST Algorithm. "histogramSort sort". Definition: An efficient 3-pass refinement of a bucket sort algorithm.
^ ^a ^b Karl-Dietrich Neubert (1998). "The FlashSort Algorithm". Retrieved 2007-11-06.

외부 링크

[1] NIST Algorithm. "interpolation sort". Definition: See histogram sort.

[2] "Histogram sort". Another variant of bucket sort known as histogram sort or counting sort adds an initial pass that counts the number of elements that will fall into each bucket using a count array. Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, leaving no space overhead for bucket storage.^{[별도 참조]}

[ReferenceA-3] "桶排序（Bucket sort）" (in Chinese). 平均時間複雜度（Average performance） $O(n+k)$ ^{[별도 참조]}

[4] "Bucket sort Average-case analysis". en.wikipedia. Note that if k is chosen to be $k=n$ , then bucket sort runs in $O(n)$ average time, given a uniformly distributed input.^{[별도 참조]}

[5] NIST Algorithm. "histogramSort sort". Definition: An efficient 3-pass refinement of a bucket sort algorithm.

[neubert_code-6] Karl-Dietrich Neubert (1998). "The FlashSort Algorithm". Retrieved 2007-11-06.

[1]

[2]

[3]

[5]

[6]

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

Search

보간 정렬

네임스페이스

더

목차

알고리즘.

보간 정렬 알고리즘

히스토그램 정렬 알고리즘

연습

보간 정렬 구현

보간 정렬 재귀 방법

히스토그램 정렬 구현

변종

보간 태그 정렬

보간 태그 정렬 알고리즘

연습

내부 보간 태그 정렬

내부 보간 태그 정렬 알고리즘

연습

$O(n)$ ) $O(n)$ 시간에서 $O(n)$ 수행된 인플레이스 정렬의 원점

유사분류법

다른 정렬 방법과 재귀 알고리즘을 혼합하는 버킷 정렬

참조

외부 링크

Search

보간 정렬

알고리즘.

보간 정렬 알고리즘

히스토그램 정렬 알고리즘

연습

보간 정렬 구현

보간 정렬 재귀 방법

히스토그램 정렬 구현

변종

보간 태그 정렬

보간 태그 정렬 알고리즘

연습

내부 보간 태그 정렬

내부 보간 태그 정렬 알고리즘

연습

O(n ) {\displaystyle O(n)}시간에서 수행된 인플레이스 정렬의 원점

유사분류법

다른 정렬 방법과 재귀 알고리즘을 혼합하는 버킷 정렬

참조

외부 링크

$O(n)$ ) $O(n)$ 시간에서 $O(n)$ 수행된 인플레이스 정렬의 원점