정렬 알고리즘

컴퓨터 과학에서 분류 알고리즘은 목록의 요소를 순서에 넣는 알고리즘이다.가장 많이 사용되는 순서는 숫자순과 사전순서순이며, 오름차순이나 내림차순이다.효율적인 정렬은 입력 데이터가 정렬 목록에 있어야 하는 다른 알고리즘(검색 및 병합 알고리즘 등)의 효율성을 최적화하는 데 중요하다.정렬은 또한 종종 데이터를 표준화하고 사람이 판독할 수 있는 출력을 생성하는 데 유용하다.

공식적으로, 정렬 알고리즘의 출력은 다음 두 가지 조건을 충족해야 한다.

1. 출력은 단조적 순서(각 원소가 필요한 순서에 따라 이전 원소보다 작거나 더 크지 않음)이다.
2. 출력은 입력의 순열(재주문, 그러나 모든 원래 요소를 유지함)이다.

최적의 효율성을 위해 입력 데이터는 순차적 액세스만 허용하는 것이 아니라 무작위 액세스가 가능한 데이터 구조에 저장해야 한다.

역사와 개념

계산 초기부터 분류 문제는 간단하고 친숙한 진술에도 불구하고 효율적으로 해결하는 복잡성 때문인지 많은 연구가 끌어왔다.1951년경 초기 분류 알고리즘의 저자들 중에는 ENIAC와 UNIVAC를 연구한 베티 홀버튼이 있었다.^[1][2]버블 분류는 빠르면 1956년에 분석되었다.^[3]20세기 중반 이후 점증적으로 최적의 알고리즘이 알려져 왔다. 새로운 알고리즘이 여전히 발명되고 있는데, 이 알고리즘은 널리 사용되는 Timsort가 2002년이고 도서관은 2006년에 처음 출판되었다.

비교 정렬 알고리즘에는 Ω(n log n) 비교의 기본 요구사항이 있다(일부 입력 시퀀스는 n log n 비교의 배수를 요구할 것이며, 여기서 n은 배열의 요소 수입니다).계수 정렬과 같이 비교에 기초하지 않은 알고리즘은 더 나은 성능을 가질 수 있다.

정렬 알고리즘은 컴퓨터 과학 입문반에서 만연해 있는데, 문제에 대한 알고리즘의 풍부함은 빅 O 표기법, 분할 및 정복 알고리즘, 힙과 바이너리 트리 같은 데이터 구조, 무작위화된 알고리즘, 베스트, 최악의, 평균 캐스 등 다양한 핵심 알고리즘 개념을 부드럽게 소개한다.e 분석, 시간-공간 트레이드오프, 상한 및 하한.

소형 어레이를 최적(최소 비교 및 스왑) 또는 고속(즉, 기계 특정 세부 정보를 고려)으로 분류하는 것은 여전히 개방형 연구 문제로서, 솔루션은 매우 작은 어레이(<20 요소)에서만 알려져 있다.이와 유사하게 (다양한 정의에 의해) 병렬 기계의 정렬이 열린 연구 주제다.

분류

정렬 알고리즘은 다음과 같이 분류할 수 있다.

• 계산 복잡성
  • 목록 크기 측면에서 가장 좋은, 최악의, 평균적인 사례 행동.일반적인 직렬 정렬 알고리즘의 경우, 좋은 동작은 O(n log n), 병렬 정렬은 O(log² n), 나쁜 동작은 O(n²)이다.직렬 분류에 대한 이상적인 동작은 O(n)이지만, 이는 일반적인 경우 가능하지 않다.최적 병렬 정렬은 O(log n)이다.
  • "in-place" 알고리즘에 대한 스왑.
• 메모리 사용량(및 다른 컴퓨터 리소스 사용)특히 일부 정렬 알고리즘은 "내부"이다.엄밀히 말하면, 내부 정렬은 정렬되는 항목을 넘어 O(1) 메모리만 필요로 한다. 때로는 O(log n) 추가 메모리가 "내부"로 간주되기도 한다.
• 재귀:어떤 알고리즘은 재귀적이거나 비재귀적이거나, 다른 알고리즘은 둘 다일 수 있다(예: 병합 정렬).
• 안정성: 안정적인 정렬 알고리즘은 동일한 키(예: 값)로 레코드의 상대적 순서를 유지한다.
• 그들이 비교 분류인지 아닌지.비교 정렬은 두 요소를 비교 연산자와 비교함으로써만 데이터를 검사한다.
• 일반 방법: 삽입, 교환, 선택, 병합 등교환 종류에는 거품 종류와 퀵소트가 있다.선택 정렬에는 사이클 정렬과 힙포트가 포함된다.
• 알고리즘이 직렬인지 병렬인지 여부.이 논의의 나머지 부분은 거의 독점적으로 직렬 알고리즘에 초점을 맞추고 직렬 작동을 가정한다.
• 적응성:입력의 사전 편차가 실행 시간에 영향을 미치는지 여부.이를 고려한 알고리즘은 적응력이 있는 것으로 알려졌다.
• 온라인: 온라인에 있는 삽입 정렬과 같은 알고리즘은 입력의 일정한 스트림을 정렬할 수 있다.

안정성

안정적인 정렬 알고리즘은 입력에 나타나는 순서대로 동일한 요소를 정렬한다.예를 들어, 오른쪽에 있는 카드 분류 예제에서 카드는 등급별로 분류되고 있으며, 정장은 무시되고 있다.이것은 원본 리스트의 여러 다른 정렬된 버전의 가능성을 허용한다.안정적인 정렬 알고리즘은 다음 규칙에 따라 이들 중 하나를 선택한다. 두 항목이 (두 개의 5 카드와 같이) 동일하다고 비교될 경우, 이들의 상대적 순서가 보존된다. 즉, 입력에서 한 항목이 다른 항목보다 먼저 오면 출력에서 다른 항목보다 먼저 나온다.

동일한 데이터 집합에서 여러 분류에 걸쳐 질서를 보존하려면 안정성이 중요하다.예를 들어, 이름과 학급 섹션으로 구성된 학생 기록이 처음에는 이름별로, 그 다음에는 학급 섹션별로 동적으로 정렬된다고 하자.두 경우 모두에 안정적인 정렬 알고리즘을 사용할 경우 클래스별 정렬 연산으로는 이름 순서가 변경되지 않는다. 불안정한 정렬을 사용하면 섹션별 정렬이 이름 순서를 섞어서 알파벳이 아닌 학생 목록이 생성될 수 있다.

보다 형식적으로, 정렬되고 있는 데이터를 값의 기록이나 튜플로 나타낼 수 있으며, 정렬에 사용되는 데이터의 부분을 키라고 한다.카드 예제에서 카드는 레코드(계단, 슈트)로 표현되며, 핵심은 순위다.같은 키를 가진 R과 S가 두 개씩 있을 때마다 R이 원래 리스트에서 S보다 앞에 나타나면 정렬 알고리즘은 안정적이다. 그러면 R은 항상 정렬된 리스트에서 S보다 앞에 나타난다.

정수와 같이, 또는 더 일반적으로, 전체 요소가 핵심인 데이터처럼 동일한 요소가 구별되지 않는 경우, 안정성은 문제가 되지 않는다.모든 키가 다르면 안정성 또한 문제가 되지 않는다.

불안정한 정렬 알고리즘은 안정성이 있도록 특별히 구현할 수 있다.이를 위한 한 가지 방법은 인위적으로 키 비교를 확장하여 키와 다른 키가 동일한 두 개체 간의 비교가 타이브레이커로 원래 입력 목록의 항목 순서를 사용하여 결정되도록 하는 것이다.그러나 이 순서를 기억하려면 추가적인 시간과 공간이 필요할 수 있다.

안정적인 정렬 알고리즘을 위한 한 가지 애플리케이션은 기본 및 보조 키를 사용하여 목록을 정렬하는 것이다.예를 들어, 정장이 주문 클럽(주문), 다이아몬드(주문), 하트(주문), 스페이드(주문자), 각 정장에 카드를 분류하고 각 정장에 카드를 순위별로 분류한다고 가정합시다.이것은 우선 카드를 등급별로 분류한 후(어떤 종류를 사용하든), 양복별로 안정적인 분류로 할 수 있다.

각각의 슈트 안에서, 안정된 종류는 이미 행해진 순위별 순서를 보존한다.이 아이디어는 임의의 수의 키로 확장될 수 있으며, radix 분류에 의해 활용된다.사전 편찬 키 비교를 사용하면 불안정한 분류로 동일한 효과를 얻을 수 있는데, 예를 들어 양복에 의해 먼저 비교한 다음, 슈트가 같으면 순위별로 비교한다.

알고리즘 비교

이 표에서 n은 정렬할 레코드 수입니다."최상", "평균" 및 "최악" 열은 각 키의 길이가 일정하므로 모든 비교, 스왑 및 기타 연산이 일정한 시간 내에 진행될 수 있다는 가정 하에 각 경우의 시간 복잡성을 제공한다."메모리"는 동일한 가정 하에서 목록 자체에서 사용하는 추가 스토리지 양을 의미한다.실행 시간과 나열된 메모리 요구 사항은 큰 O 표기법 안에 있으므로 로그의 기초는 중요하지 않다.표기 로그² n은 (log n)을 의미한다.²

비교 정렬

아래는 비교 분류표다.비교 정렬은 평균적으로 O(n log n)보다 더 잘 수행될 수 없다.^[4]

비교 정렬

이름	베스트	평균	최악	기억력	안정적	방법	기타 노트
퀵소트	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle \log n}$	아니요.	파티셔닝	Quicksort는 대개 O(log n) 스택 공간으로 인플레이스 처리된다.[5][6]
병합 정렬	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	네	병합	고도로 병렬 가능(헝가리 3인 알고리즘을 사용한 최대 O(log n)).[7]
내부 병합 정렬	—	—	${\displaystyle n\log ^{2}n}$	1	네	병합	안정적인 인플레이스 합병을 기반으로 안정적 소트로서 구현 가능.[8]
인트로소트	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	아니요.	파티셔닝 & 선택	여러 STL 구현에 사용됨.
힙스포트	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	아니요.	선택
삽입 정렬	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	네	삽입	최악의 경우 d inversion이 있는 시퀀스보다 O(n + d).
블록 정렬	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	네	삽입 & 병합	블록 기반 $O{\displaystyle (n}$) ${\displaystyle O(n)}$ 내부$$ 병합 알고리즘을[9] 상향 병합 정렬과 결합하십시오.
팀소트	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	네	삽입 & 병합	데이터가 이미 정렬되었거나 역순으로 정렬된 경우 n-1 비교
선택 정렬	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	아니요.	선택	$O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O(n)}$개의$$ 추가 공간, 링크된 목록을 사용할 때 또는 두 항목을 스와핑하는 대신 삽입 정렬의 변형으로 만들 때 안정적이다.[10]
큐빅	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	네	삽입	데이터가 이미 정렬되었거나 역순으로 정렬된 경우 n-1 비교
조개류	${\displaystyle n\log n}$	${\displaystyle n^{4/3}}$	${\displaystyle n^{3/2}}$	1	아니요.	삽입	작은 코드 크기.
버블 정렬	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	네	교환	작은 코드 크기.
교환 정렬	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	네	교환	작은 코드 크기.
트리 정렬	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n}$ ${\displaystyle \log }$ ${\displaystyle ▼n}$ ${\displaystyle n\log$ n$\}($균형 조정)	n	네	삽입	자체 균형 이진 검색 트리를 사용하는 경우.
사이클 정렬	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	아니요.	선택	이론적으로 최적의 쓰기 횟수로 인플레이스.
라이브러리 정렬	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	n	아니요.	삽입	도핑된 삽입 정렬과 유사함.높은 확률의 시간 범위를 가진 입력을 임의로 허용해야 하므로 안정성이 떨어진다.
인내 정렬	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n	아니요.	삽입 & 선택	O(n log n)에서 가장 오래 증가하는 모든 부분 검색.
스무스소트	n	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	아니요.	선택	전통적인 이진 힙이 아닌 레오나르도 시퀀스에 기초한 힙포트의 적응형 변형.
스트랜드 정렬	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	n	네	선택
토너먼트 정렬	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n[11]	아니요.	선택	힙소트의 변형.
칵테일 셰이커 분류	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	네	교환	목록 끝에서 작은 값을 잘 다루는 버블코트의 변종류
콤 정렬	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	아니요.	교환	평균적으로 거품보다 빠르다.
Gnome sort	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	네	교환	작은 코드 크기.
홀수-짝수 정렬	n	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	네	교환	병렬 프로세서에서 쉽게 실행 가능.

비비교 분류

다음 표에서는 비교 정렬이 아닌 정수 정렬 알고리즘과 기타 정렬 알고리즘을 설명한다.따라서 Ω(n log n)으로 제한되지 않는다.^[12]아래의 복잡성은 정렬할 항목 n개, 크기 k, 숫자 d 및 r의 키와 함께 정렬할 숫자의 범위를 가정한다.이들 중 다수는 모든 항목이 고유한 키 값을 가질 정도로 키 크기가 크다는 가정 하에, n ≪ 2가^k "보다 훨씬 작음"을 의미한다고 가정한다.In the unit-cost random-access machine model, algorithms with running time of ${\displaystyle \scriptstyle n\cdot {\frac {k}{d}}}$, such as radix sort, still take time proportional to Θ(n log n), because n is limited to be not more than ${\displaystyle 2^{\frac {k}{d}}}$, and a larger number of elements to sor그들을 기억 속에 저장하기 위해서는 더 큰 k가 필요할 것이다.^[13]

비비교 분류

이름	베스트	평균	최악	기억력	안정적	n ≪ 2k	메모들
비둘기홀 정렬	—	${\displaystyle n+2^{k}}$	${\displaystyle n+2^{k}}$	${\displaystyle 2^{k}}$	네	네	비정수자를 정렬할 수 없음.
버킷 정렬(고유 키)	—	${\displaystyle n+k}$	${\displaystyle n^{2}\cdot k}$	$디스플레이 스타일 n\cdot k}$	네	아니요.	배열의 도메인에서 요소의 균일한 분포를 가정한다.[14] 또한 비정수자를 정렬할 수 없음
버킷 정렬(integer 키)	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	네	네	r이 $O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O(n$인 경우, $평균{\displaystyle }$ 시간 복잡성은 ${\displaystyle O}$( n${\displaystyle }$) ${\displaystyle$ O$(n)}$이다$.$[15]
카운팅 정렬	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	네	네	r이 $O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O(n$인 경우, $평균{\displaystyle }$ 시간 복잡성은 ${\displaystyle O}$( n${\displaystyle }$) ${\displaystyle$ O$(n)}$이다$.$[14]
LSD Radix 정렬	${\displaystyle n}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	네	아니요.	${\displaystyle \frac{k}{}}$ ${\displaystyle \frac{d}{}}$ ${\$frac {$k}{d}}$ 재귀 수준$$,[14][15] 카운트 어레이의 경우 2개d. 대부분의 분포 정렬과 달리, 이것은 부동 소수점, 음수 등을 정렬할 수 있다.
MSD Radix 정렬	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	네	아니요.	스테이블 버전은 모든 빈을 담기 위해 n 크기의 외부 배열을 사용한다. LSD 변종과 마찬가지로 비정수자를 분류할 수 있다.
MSD Radix 정렬(내부)	—	${\displaystyle n\cdot {\frac {k}{1}}$	${\displaystyle n\cdot {\frac {k}{1}}$	${\displaystyle 2^{1}$	아니요.	아니요.	d=1 in-place, ${\displaystyle k\mathrm{}}$/ 1 ${\displaystyle k/1}$재귀$$ 수준, 개수 배열 없음.
스프레스포트	n	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot \왼쪽{\frac {k}{s}}+d}\오른쪽)}$	${\displaystyle {\frac {k}{d}}\cdot 2^{d}}$	아니요.	아니요.	점근법은 n ≪ 2라는k 가정에 근거하지만 알고리즘에는 이를 필요로 하지 않는다.
버스토트	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	아니요.	아니요.	문자열을 정렬하기 위한 radix 정렬보다 상수 요인이 더 우수함.그러나 공통적으로 접하는 문자열의 세부사항에 다소 의존한다.
플래시소트	n	${\displaystyle n+r}$	${\displaystyle n^{2}}$	n	아니요.	아니요.	어레이의 도메인에서 요소를 균일하게 배포하여 선형 시간으로 실행해야 함.분포가 극도로 치우친 경우 기본 정렬이 2차인 경우 2차 분포가 될 수 있다(일반적으로 삽입 정렬임).인플레이스 버전이 안정적이지 않다.
우편배달부 분류	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	—	아니요.	MSD Radix Sort와 매우 유사하게 작동하는 버킷 정렬의 변형.사후 서비스 니즈에 한정됨.

샘플 포트는 데이터를 여러 버킷으로 효율적으로 배포한 다음 여러 프로세서에 정렬을 전달하여 비교가 되지 않는 모든 정렬을 병렬화하는 데 사용할 수 있으며, 버킷이 이미 서로 정렬되어 있으므로 병합할 필요가 없다.

다른이들

어떤 알고리즘은 무한 실행 시간이 있는 보고 포트와 O(n^2.7) 실행 시간이 있는 스투지 분류와 같이 위에서 논의한 알고리즘에 비해 느리다.이러한 분류는 보통 알고리즘의 실행 시간이 어떻게 추정되는지를 증명하기 위해 교육 목적으로 설명된다.다음 표에서는 성능이 극도로 저하되거나 하드웨어 전문 요구사항으로 인해 전통적인 소프트웨어 맥락에서 실제 사용하기에 비실용적인 일부 정렬 알고리즘을 설명한다.

이름	베스트	평균	최악	기억력	안정적	비교	기타 노트
비드 정렬	n	S	S	${\displaystyle n^{2}}$	해당 없음	아니요.	양의 정수만 사용할 수 있음.보증 $O{\displaystyle }$ (${\displaystyle n}$)${\displaystyle O(n)}$시간$$ 내에 실행하려면 전문 하드웨어가 필요하다.소프트웨어 구현 가능성도 있지만 실행 시간은 $O{\displaystyle }$( ${\displaystyle S}$) ${\displaystyle O(S)}$이며$,$ 여기서 S는 정렬할 모든 정수의 합이며, 작은 정수의 경우 선형인 것으로 간주할 수 있다.
심플 팬케이크 소트	—	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle \log n}$	아니요.	네	카운트는 플립 수입니다.
스파게티(폴) 분류	n	n	n	${\displaystyle n^{2}}$	네	폴링	이것은 항목의 순서를 정렬하기 위한 선형 시간 아날로그 알고리즘으로, O(n) 스택 공간이 필요하며, 정렬이 안정적이다.이를 위해서는 n개의 병렬 프로세서가 필요하다.스파게티 sort#Analysis를 참조하십시오.
정렬 네트워크	다르다	다르다	다르다	다르다	다양함(안정적인 정렬 네트워크는 더 많은 비교가 필요함)	네	비교 순서는 고정된 네트워크 크기를 기준으로 미리 설정한다.[disputed – discuss]
비토닉 정렬기	${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$ ${\displaystyle \log ^{2}n}$ 병렬$$	${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$ ${\displaystyle \log ^{2}n}$ 병렬$$	${\displaystyle n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle n\log ^{2}n}$ 비필수$$	1	아니요.	네	정렬 네트워크의 효과적인 변화.[disputed – discuss]
보고소트	n	$(n\displaystyle)(n\displayn!)}$	Unbounded (inbound),${\displaystyle }$(${\displaystyle n}$ ${\displaystyle \times }$ ${\displaystyle n!}$) ${\displaystyle (n\n!)}($예상)	1	아니요.	네	무작위 셔플링.예상된 베스트 케이스 런타임도 끔찍하기 때문에 예시 목적으로만 사용된다.[16]
스투지 분류	${\displaystyle n^{\log 3/\log 1.5}$	${\displaystyle n^{\log 3/\log 1.5}$	${\displaystyle n^{\log 3/\log 1.5}$	n	아니요.	네	O(n) = O(nlog 3 / log 1.5 2.7095...)의 시간 복잡성을 가진 대부분의 정렬 알고리즘(순진한 알고리즘도 있음)보다 느리게 만들 수 있으며, 또한 정렬 네트워크이기도 하다.
슬로우토트	${\displaystyle n^{\log n}}$	${\displaystyle n^{\log n}}$	${\displaystyle n^{\log n}}$	n	아니요.	네	곱셈과 항복 알고리즘, 분열과 정복 알고리즘과 반대어.

이론 컴퓨터 과학자들은 추가 제약조건을 가정할 때 O(n log n) 시간 복잡성보다 더 나은 시간을 제공하는 기타 분류 알고리즘을 다음과 같이 상세하게 가지고 있다.

• 토럽 알고리즘은 크기가 유한한 도메인에서 키를 정렬하기 위한 임의 알고리즘으로 O(n log n) 시간과 O(n) 공간을 차지한다.^[17]
• $O{\displaystyle (n}$ ${\displaystyle \sqrt{\log }}$ ${\displaystyle \sqrt{}}$ ${\displaystyle \sqrt{\log }}$ ${\displaystyle \sqrt{n}}$) ${\$ O$\left(n{\sqrt {\log \log n}\right)}$ 기대$$ 시간 및 O(n) 공간을 차지하는 임의 정수 정렬 알고리즘.^[18]

인기 정렬 알고리즘

정렬 알고리즘이 많은 반면, 실제 구현에서는 몇 가지 알고리즘이 우세하다.삽입 정렬은 소형 데이터 세트에 널리 사용되는 반면, 대형 데이터 세트의 경우 주로 힙서트, 병합 정렬 또는 퀵서트 등 무증상적으로 효율적인 정렬이 사용된다.효율적인 구현은 일반적으로 전체 분류에 대해 점증적으로 효율적인 알고리즘과 재귀 하단에 있는 작은 리스트에 대한 삽입 정렬을 결합하여 하이브리드 알고리즘을 사용한다.고도로 조정된 구현에서는 Android, Java 및 Python에서 사용되는 Timsort(머지 정렬, 삽입 정렬 및 추가 로직)와 같은 보다 정교한 변형과 일부 C++ 정렬 구현 및 에서 사용되는 인트로포트(퀵소트 및 힙소트)를 사용한다.NET,

고정된 간격의 숫자와 같이 더 제한적인 데이터의 경우 카운트 소트 소트 또는 라딕스 소트 같은 분포 소트들이 널리 사용된다.버블 분류와 변형은 실제로 거의 사용되지 않지만, 일반적으로 교수법과 이론적 논의에서 발견된다.

물리적으로 사물을 분류할 때(종이, 시험, 책 등) 사람들은 직관적으로 작은 세트에 삽입 서류를 사용한다.더 큰 세트의 경우, 사람들은 종종 첫 번째 버킷(초기 문자 등)을 사용하며, 여러 버킷을 사용하면 매우 큰 세트의 실용적인 정렬을 할 수 있다.종종 바닥이나 넓은 면적에 물체를 펼쳐 놓는 것과 같이 공간은 상대적으로 저렴하지만, 운영은 비용이 많이 들고, 특히 물체를 먼 곳으로 이동시키므로 참조의 지역성이 중요하다.병합 정렬은 물리적 물체에도 실용적이며, 특히 목록마다 하나씩 두 손을 사용할 수 있고, 힙소트나 퀵소트 같은 다른 알고리즘은 인간 사용에 적합하지 않다.공간을 남기는 삽입 분류의 변형인 라이브러리 분류와 같은 다른 알고리즘도 물리적 사용에 실용적이다.

심플 소트

가장 간단한 두 종류는 삽입 분류와 선택 분류인데, 두 종류 모두 오버헤드가 낮기 때문에 작은 데이터에서는 효율적이지만 큰 데이터에서는 효율적이지 않다.삽입 분류는 일반적으로 거의 정렬된 데이터에 대한 비교가 적고 성능이 좋아 실제에서는 선택 분류보다 속도가 빠르기 때문에 선호되지만 선택 분류는 쓰기가 적어서 쓰기 성능이 제한적인 요인일 때 사용된다.

삽입 정렬

삽입 정렬은 작은 목록과 대부분 정렬된 목록에 대해 비교적 효율적인 간단한 정렬 알고리즘으로, 보다 정교한 알고리즘의 일부로 자주 사용된다.리스트에서 요소들을 하나씩 꺼내어 정확한 위치에 넣으면서 우리가 지갑에 돈을 넣는 방식과 비슷한 새로운 정렬된 리스트에 넣는 방식으로 작동한다.^[19]배열에서, 새로운 목록과 나머지 요소들은 배열의 공간을 공유할 수 있지만, 삽입은 비용이 많이 들기 때문에 다음 요소들을 하나씩 옮겨야 한다.쉘포트는 대형 리스트에 더 효율적인 삽입 분류의 변형이다.

선택 정렬

선택 정렬은 인플레이스 비교 정렬이다.O(n²) 복잡성이 있어 대형 리스트에서 비효율적이며, 일반적으로 유사한 삽입 종류보다 성능이 떨어진다.선택 분류는 단순성으로 주목받으며, 특정 상황에서 더 복잡한 알고리즘에 비해 성능상의 이점도 있다.

알고리즘은 최소값을 찾아 첫 번째 위치의 값과 교환하고 목록의 나머지 부분에 대해 이 단계를 반복한다.^[20]그것은 n 스왑에 지나지 않으며, 따라서 스와핑이 매우 비쌀 때 유용하다.

효율적인 분류

실용적인 일반 정렬 알고리즘은 거의 항상 평균 시간 복잡성(그리고 일반적으로 최악의 경우 복잡성) O(n log n)을 가진 알고리즘에 기초하고 있으며, 그 중 가장 일반적인 것은 힙소트, 병합 정렬, 퀵소트다.각각 장점과 단점이 있는데, 가장 중요한 것은 병합 분류의 단순 구현은 O(n)의 추가 공간을 사용하며, 퀵소트의 단순 구현은 O(n²) 최악의 복잡성을 가지고 있다는 점이다.이러한 문제들은 좀 더 복잡한 알고리즘의 비용으로 해결되거나 개선될 수 있다.

이러한 알고리즘은 무작위 데이터에 대해서는 점증적으로 효율적이지만 실제 데이터에 대한 실질적인 효율을 위해 다양한 수정이 사용된다.첫째로, 이러한 알고리즘의 오버헤드는 작은 데이터에서 중요하기 때문에 종종 하이브리드 알고리즘을 사용하며, 데이터가 충분히 작으면 삽입 정렬로 전환된다.둘째, 알고리즘은 이미 정렬된 데이터나 거의 정렬된 데이터에서 저조한 성능을 보이는 경우가 많다. 이러한 데이터는 실제 데이터에서 흔히 볼 수 있으며 적절한 알고리즘에 의해 O(n) 시간으로 정렬될 수 있다.마지막으로, 그것들 또한 불안정할 수 있고, 안정성은 종종 어떤 종류의 바람직한 재산이다.따라서 팀소트(merge sort based)나 인트로포트(quicksort based, back to hapsort)와 같이 보다 정교한 알고리즘이 채택되는 경우가 많다.

병합 정렬

병합 정렬은 이미 정렬된 목록을 새 정렬된 목록으로 쉽게 병합할 수 있는 이점을 활용한다.두 요소(즉, 1과 2를 비교하고 3과 4를 비교하는 것)와 1이 2가 지나면 1이 오면 교환하는 것으로 시작한다.그런 다음 두 개의 결과 목록을 각각 4개의 목록으로 병합한 다음, 4개의 목록 등을 병합한다. 마지막으로 두 개의 목록이 최종 정렬된 목록으로 병합될 때까지.^[21]여기서 설명한 알고리즘 중에서 가장 최악의 경우 실행 시간이 O(n log n)이기 때문에 가장 큰 목록으로 잘 확장되는 것은 이번이 처음이다.무작위 액세스가 아닌 순차적 액세스만 요구하기 때문에 배열뿐 아니라 목록에도 쉽게 적용된다.그러나 O(n) 공간 복잡성이 추가되며, 단순 구현에는 많은 수의 복사가 수반된다.

Merge sort는 프로그래밍 언어 Python과^[22] Java(JDK7^[23] 기준)에서 표준 정렬 루틴에 사용되는 정교한 알고리즘 Timsort에서 사용되었기 때문에 실제 구현을 위한 비교적 최근에 인기가 급상승했다.Merge sort 자체는 ^[24]Perl에서 표준 루틴이며, JDK1.3에서는 적어도 2000년부터 Java에서 사용되고 있다.^[25]

힙스포트

힙소트는 선택 분류의 훨씬 더 효율적인 버전이다.또한 목록의 가장 큰(또는 가장 작은) 요소를 결정하여 목록의 끝(또는 시작)에 배치한 다음 나머지 목록으로 계속하는 방식으로 작동하지만, 특수한 유형의 이진 트리인 힙이라는 데이터 구조를 사용하여 이 작업을 효율적으로 수행한다.^[26]데이터 목록이 힙으로 만들어지면 루트 노드는 가장 큰 요소(또는 가장 작은 요소)가 된다.제거 후 목록 끝에 배치하면 힙이 재배열되므로 남아 있는 가장 큰 요소가 루트로 이동한다.힙을 사용하면 단순 선택 정렬에서와 같이 선형 스캔의 O(n) 대신 O(log n) 시간이 소요된다.이로써 햅소트는 O(n log n) 시간에 실행될 수 있으며, 이 또한 최악의 경우 복잡성이 된다.

퀵소트

Quicksort는 분할 및 정복 알고리즘으로, 분할 작업에 의존하는 알고리즘으로, 배열을 분할하기 위해 피벗이라는 요소가 선택된다.^[27][28]피벗보다 작은 모든 원소는 그 전에 이동되고 그 후에 더 큰 원소는 모두 이동된다.이것은 선형적인 시간과 장소에 효율적으로 수행될 수 있다.그런 다음 하위 목록과 상위 하위 목록을 반복적으로 정렬한다.이는 O(n log n)의 평균 시간 복잡성을 산출하며 오버헤드가 낮으므로 널리 사용되는 알고리즘이다.퀵소트의 효율적인 구현(인플레이스 파티셔닝 포함)은 일반적으로 불안정하고 다소 복잡하지만 실제로 가장 빠른 정렬 알고리즘에 속한다.퀵소트는 O(log n) 공간 사용과 함께 가장 인기 있는 정렬 알고리즘 중 하나이며 많은 표준 프로그래밍 라이브러리에서 사용할 수 있다.

Quicksort에 대한 중요한 주의사항은 그것의 최악의 경우 성능은 O(n²)이며, 이는 드물지만, 순진한 구현(피벗으로 첫 번째 또는 마지막 요소를 선택)에서 이것은 정렬된 데이터에 대해 발생한다는 것이다. 이는 일반적인 경우다.따라서 퀵소트에서 가장 복잡한 문제는 좋은 피벗 요소를 선택하는 것이다. 피벗의 선택이 지속적으로 좋지 않으면 O(n²) 성능이 현저히 느려질 수 있지만 피벗을 잘 선택하면 O(n log n) 성능이 나타나는데, 이는 무증상 최적이다.예를 들어 각 단계에서 중앙값을 피벗으로 선택하면 알고리즘이 O(n log n)에서 작동한다.그러나 중위수 선택 알고리즘의 중위수와 같은 중위수를 찾는 것은 정렬되지 않은 리스트에 대한 O(n) 연산이기 때문에 정렬로 상당한 오버헤드가 발생한다.실제로 랜덤 피벗을 선택하면 거의 확실히 O(n log n) 성능이 발생한다.

조개류

셸포트는 1959년 도널드 셸에 의해 발명되었다.^[29]한 번에 한 위치 이상 순서 요소에서 벗어나 삽입 시 개선된다.Shellsort 뒤에 있는 개념은 삽입 $정렬이{\displaystyle }$ O${\displaystyle (k}$ ${\displaystyle n}$) ${\displaystyle O(kn)}$시간에$$ 수행된다는 것인데, 여기서 k는 두 외부 요소 사이의 가장 큰 거리다.이는 일반적으로 O(n²)로 수행하지만, 대부분 정렬된 데이터의 경우 몇 개의 요소만 제자리에 있지 않은 상태에서 더 빨리 수행된다는 것을 의미한다.그래서 먼저 원소를 멀리 분류하고, 정렬할 원소들 사이의 간격을 점진적으로 줄임으로써 최종 분류는 훨씬 더 빨리 계산한다.하나의 구현은 데이터 시퀀스를 2차원 배열로 배열한 다음 삽입 정렬을 사용하여 배열의 열을 정렬하는 것으로 설명할 수 있다.

Shellsort의 최악의 시간 복잡성은 개방형 문제로서 사용된 간격 순서에 따라 달라지며, 알려진 복잡성은 O(n²)부터 O(n^4/3) 및 θ(n log² n)까지 다양하다.이는 쉘포트가 제자리에 있고, 상대적으로 적은 양의 코드만 필요하며, 콜 스택을 사용할 필요가 없다는 사실과 결합되어 임베디드 시스템이나 운영 체제 커널과 같이 메모리가 프리미엄인 상황에서 유용하게 쓰인다.

버블 정렬 및 변형

버블 분류와 쉘포트 분류와 칵테일 분류와 같은 변형들은 간단하고 매우 비효율적인 분류 알고리즘이다.분석의 용이성 때문에 입문서에서 자주 볼 수 있지만 실전에 활용되는 경우는 드물다.

버블 정렬

버블 정렬은 간단한 정렬 알고리즘이다.알고리즘은 데이터 집합의 시작 부분에서 시작한다.처음 두 요소를 비교하고, 첫 번째 요소가 두 번째 요소보다 크면 교환한다.데이터 집합의 끝에 인접한 각 요소 쌍에 대해 이 작업을 계속한다.그런 다음 처음 두 요소에서 다시 시작하여 마지막 패스에서 스왑이 발생하지 않을 때까지 반복한다.^[30]이 알고리즘의 평균 시간과 최악의 경우 성능은 O(n²)이므로 정렬되지 않은 대용량 데이터 세트를 정렬하는 데 거의 사용되지 않는다.버블 분류는 적은 수의 항목(증상 비효율이 높은 벌금이 아닌 경우)을 분류하는 데 사용될 수 있다.버블 정렬은 또한 거의 정렬된 모든 길이(즉, 원소가 유의하게 제자리에 있지 않음)의 리스트에서 효율적으로 사용될 수 있다.예를 들어, 한 위치(예: 0123546789 및 1032547698)만 원소가 제자리에 있지 않으면(예: 0123546789 및 1032547698) 버블 분류의 교환은 첫 번째 패스에서 그것들을 순서대로 얻을 것이고, 두 번째 패스는 모든 원소를 순서대로 찾을 것이므로, 분류는 2n 시간밖에 걸리지 않을 것이다.

^[31]

콤 정렬

콤 소트(Comb sort)^[32]는 버블 소트(Bubble sort)를 기반으로 한 비교적 단순한 분류 알고리즘으로, 원래 1980년 Wwodzimierz Dobosiewicz가 설계했다.이후 스티븐 레이시와 리처드 박스에 의해 1991년 4월에 발행된 바이트 매거진 기사로 재발견되어 대중화되었다.기본적인 아이디어는 거북이, 즉 목록 끝 근처의 작은 값들을 제거하는 것인데, 이것은 거품 속에서 분류가 엄청나게 느리기 때문이다. (목록 시작 주변의 큰 값들은 거품 분류에 문제를 일으키지 않는다) 그것은 처음에 서로 일정한 거리인 요소들을 arr에서 교환함으로써 이것을 성취한다.ay, 원소가 서로 인접해 있을 때에만 교환하는 것이 아니라, 일반 버블 종류로 작동할 때까지 선택한 거리를 축소하는 것이다.따라서 쉘포트를 서로 일정한 간격을 두고 요소들을 서로 교환하는 삽입 분류의 일반화된 버전으로 생각할 수 있다면 빗 분류는 버블 분류에 적용되는 일반화라고 생각할 수 있다.

교환 정렬

알고리즘이 사실상 구별되긴 하지만, 교환 분류는 버블 분류와 혼동되기도 한다.^[33][34]교환 정렬은 첫 번째 요소를 위의 모든 요소와 비교하고, 필요한 경우 스와핑하여 첫 번째 요소가 최종 정렬 순서에 대해 올바른지 확인한 다음, 두 번째 요소에 대해서도 동일한 작업을 진행하는 방식으로 진행된다.리스트가 이미 정렬된 경우 버블 정렬이 한 번의 통과로 감지할 수 있는 이점은 부족하지만 최악의 경우 일정한 요인(정렬할 데이터에 대한 패스 1회, 총 비교 횟수 절반)에 의한 버블 정렬보다 빠를 수 있다.다른 단순한 O(n²) 분류와 마찬가지로 매우 작은 데이터 집합에 비해 상당히 빠를 수 있지만 일반적인 삽입 분류는 더 빠를 것이다.

분포 정렬

분포 정렬은 데이터가 입력에서 여러 중간 구조로 분산된 후 출력물에 수집되어 배치되는 정렬 알고리즘을 가리킨다.예를 들어 버킷 정렬과 플래시 정렬 모두 배포 기반 정렬 알고리즘이다.분산 정렬 알고리즘은 단일 프로세서에서 사용할 수도 있고, 분산 알고리즘이 될 수도 있는데, 분산 알고리즘은 개별 서브셋이 서로 다른 프로세서에서 별도로 정렬된 다음 결합된다.이것은 너무 커서 단일 컴퓨터의 메모리에 맞지 않는 데이터의 외부 정렬을 가능하게 한다.

카운팅 정렬

카운팅 정렬은 각 입력이 특정 가능성 집합인 S에 속하는 것으로 알려진 경우에 적용된다.알고리즘은 O(S + n) 시간과 O(S ) 메모리로 실행되며 여기서 n은 입력의 길이다.크기 S의 정수 배열을 만들고 ith bin을 사용하여 입력에서 s의 ith 멤버의 발생 횟수를 계산하는 방식으로 작동한다.그런 다음 각 입력은 해당 빈의 값을 증가시켜 계산한다.그 후, 모든 입력을 순서대로 배열하기 위해 카운팅 배열을 반복한다.이 정렬 알고리즘은 알고리즘이 효율적이기 위해서는 S가 상당히 작아야 하기 때문에 사용할 수 없는 경우가 많지만, 매우 빠르고 n이 증가함에 따라 큰 점근거동을 나타낸다.그것은 또한 안정적인 행동을 제공하도록 수정될 수 있다.

버킷 정렬

버킷 정렬은 배열을 한정된 수의 버킷으로 분할하여 카운팅 정렬을 일반화하는 분할 및 정복 정렬 알고리즘이다.그런 다음 각 버킷은 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 재귀적으로 적용하여 개별적으로 정렬된다.

버킷 정렬은 데이터 세트의 요소가 모든 버킷에 고르게 분포되어 있을 때 가장 잘 작동한다.

라딕스 분류

라딕스 정렬은 개별 숫자를 처리하여 숫자를 정렬하는 알고리즘이다.n k자릿수로 구성된 숫자는 각각 O(n · k) 시간으로 정렬된다.Radix 정렬은 가장 작은 숫자(LSD)에서 시작하거나 가장 중요한 숫자(MSD)에서 시작하는 각 숫자의 숫자를 처리할 수 있다.LSD 알고리즘은 안정적인 정렬을 사용하여 상대적인 순서를 유지하면서 먼저 리스트를 최하위 자릿수로 정렬한다.그런 다음 다음 다음 숫자를 기준으로 정렬하고, 가장 작은 숫자에서 가장 중요한 숫자까지 정렬하여 정렬된 목록으로 끝낸다.LSD radix 정렬은 안정적인 정렬을 사용해야 하지만 MSD radix 정렬 알고리즘은 그렇지 않다(안정적인 정렬을 원하지 않는 경우).인플레이스 MSD radix 정렬이 안정적이지 않다.계산 정렬 알고리즘은 라딕스 분류에 의해 내부적으로 사용되는 것이 일반적이다.작은 빈에 삽입 정렬을 사용하는 것과 같은 하이브리드 정렬 접근법은 라딕스 정렬의 성능을 크게 향상시킨다.

메모리 사용 패턴 및 인덱스 정렬

정렬할 배열의 크기가 사용 가능한 기본 메모리에 접근하거나 초과하여 디스크나 스왑 공간을 (매우 느리게) 사용해야 하는 경우, 정렬 알고리즘의 메모리 사용 패턴이 중요해지고, 어레이가 RAM에 쉽게 맞았을 때 상당히 효율적이었을 수 있는 알고리즘이 비현실적으로 될 수 있다.이 시나리오에서, 비교의 총 횟수는 (상대적으로) 덜 중요해지고, 디스크에서 복사하거나 디스크로 교환해야 하는 메모리 섹션의 횟수가 알고리즘의 성능 특성을 지배할 수 있다.따라서 디스크 속도에 비해 거의 즉각적으로 발생하는 시스템 버스 속도(또는 CPU 속도에서도 캐싱과 함께)에서 가까운 요소와 서로 비교하기 때문에 패스의 수와 비교의 로컬리제이션이 원시 비교 횟수보다 더 중요할 수 있다.

예를 들어, 널리 사용되는 재귀적 퀵소트 알고리즘은 적절한 RAM으로 상당히 합리적인 성능을 제공하지만, 어레이의 일부를 복사하는 재귀적 방법 때문에 RAM에 맞지 않을 때는 훨씬 덜 실용적이 된다. 왜냐하면, 이는 디스크로 복사하거나 디스크로 이동하는 많은 저속 복사 작업을 야기할 수 있기 때문이다.이 시나리오에서는 다른 알고리즘이 더 많은 총체적 비교를 요구하더라도 더 바람직할 수 있다.

관계형 데이터베이스와 같은 복잡한 레코드(예: 관계형 데이터베이스)가 상대적으로 작은 키 필드에 의해 정렬되고 있을 때 잘 작동하는 이 문제를 해결하는 한 가지 방법은 전체 배열보다는 배열로 색인을 만든 다음 색인을 정렬하는 것이다.(그 후 전체 배열의 정렬된 버전은 인덱스에서 판독하는 하나의 패스로 제작될 수 있지만, 정렬된 인덱스를 가지는 것이 적절하기 때문에 그마저도 불필요할 때가 많다.전체 어레이보다 인덱스가 훨씬 작기 때문에 전체 어레이가 그렇지 않은 메모리에 쉽게 들어맞을 수 있어 디스크 스왑 문제가 효과적으로 제거된다.이 절차를 "태그 정렬"이라고도 한다.^[35]

메모리 크기 문제를 극복하기 위한 또 다른 기법은 외부 정렬을 사용하는 것인데, 예를 들어 두 알고리즘을 각각의 강도를 이용하여 전체적인 성능을 향상시키는 방법으로 결합하는 것이다.예를 들어, 배열을 RAM에 맞는 크기의 청크로 세분할 수 있고, 효율적인 알고리즘(예: 퀵소트)을 사용하여 정렬된 각 청크의 내용물이며, 병합 정렬에서 사용되는 것과 유사한 k-way 병합을 사용하여 결과가 병합될 수 있다.이것은 전체 리스트에서 병합 정렬 또는 퀵 정렬을 수행하는 것보다 빠르다.^[36][37]

기법도 결합할 수 있다.시스템 메모리를 훨씬 초과하는 매우 큰 데이터 집합을 정렬하기 위해서는, 심지어 인덱스도 가상 메모리와 합리적으로 수행하도록 설계된 알고리즘이나, 즉 필요한 스와핑의 양을 줄이기 위해 고안된 알고리즘의 조합을 사용하여 정렬해야 할 수 있다.

관련 알고리즘

관련 문제로는 대략적인 정렬(정확한 순서의 양 이내로 시퀀스를 정렬), 부분 정렬(목록의 가장 작은 요소만 정렬하거나, 가장 작은 요소를 찾지만 정렬되지 않음) 및 선택(k번째 가장 작은 요소 계산)이 있다.이러한 알고리즘은 전체 정렬에 의해 비효율적으로 해결될 수 있지만, 보다 효율적인 알고리즘이 존재하며, 종종 정렬 알고리즘을 일반화함으로써 도출된다.퀵소트 관련 퀵셀렉트(quick selection)가 가장 눈에 띈다.반대로, 어떤 정렬 알고리즘은 선택 알고리즘의 반복 적용에 의해 도출될 수 있다; 퀵소트 및 퀵셀렉트는 양쪽에서 재귀하는 (퀵소트, 분할 및 정복) 또는 한쪽에서(퀵셀렉트, 감소 및 정복)하는 경우에만 다른 동일한 선회 움직임으로 볼 수 있다.

분류 알고리즘의 일종의 반대말은 셔플링 알고리즘이다.이것들은 난수원을 요구하기 때문에 근본적으로 다르다.셔플링은 정렬 알고리즘, 즉 무작위 정렬을 통해 구현될 수 있다. 즉, 목록의 각 요소에 무작위 번호를 할당하고 난수를 기준으로 정렬한다.그러나 이것은 일반적으로 실제로 수행되지 않으며, 잘 알려진 간단하고 효율적인 슈플링 알고리즘인 피셔-예이츠 슈플링이 있다.

정렬 알고리즘은 여러 상황에서 순서를 찾는 데 효과적이지 않다.일반적으로 요소들이 신뢰할 수 있는 비교 기능(투표 시스템과 같은 크라우드소스 선호)이 없을 때, 비교는 매우 비용이 많이 들거나(스포츠), 모든 기준(검색 엔진)에 대해 모든 요소를 쌍으로 비교할 수 없을 때 가능하다.이 경우 보통 문제를 순위라고 하며, 목표는 비교나 순위에서 유추된 확률에 따라 일부 기준에 대해 "최상의" 결과를 찾는 것이다.일반적인 예로는 체스에서 선수들이 엘로 등급제로 순위를 매기고, 랭킹은 정렬 알고리즘 대신 토너먼트 시스템에 의해 결정된다.

참고 항목

• 데이터 정렬 – 작성된 정보를 표준 순서로 결합
• K-모양순서
• 쌍 비교
• 슈워츠 변환
• 검색 알고리즘 – 검색 문제를 해결하는 모든 알고리즘
• Quantum 정렬 – 양자 컴퓨터용 알고리즘 정렬

참조

추가 읽기

• Knuth, Donald E. (1998), Sorting and Searching, The Art of Computer Programming, vol. 3 (2nd ed.), Boston: Addison-Wesley, ISBN 0-201-89685-0
• Sedgewick, Robert (1980), "Efficient Sorting by Computer: An Introduction", Computational Probability, New York: Academic Press, pp. 101–130, ISBN 0-12-394680-8

외부 링크

Wikibook 알고리즘 구현에는 알고리즘 정렬을 주제로 한 페이지가 있다.

위키북 A레벨 수학은 알고리즘 정렬을 주제로 한 페이지를 가지고 있다.

위키미디어 커먼즈에는 정렬 알고리즘과 관련된 미디어가 있다.

• 웨이백 머신에서 알고리즘 애니메이션 정렬(2015년 3월 3일 보관)
• 순차 및 병렬 정렬 알고리즘 – 여러 정렬 알고리즘의 설명 및 분석
• 알고리즘 사전, 데이터 구조 및 문제 – 알고리즘, 기술, 공통 기능 및 문제 사전
• 알고리즘 정렬에 대한 약간 회의적인 견해 – 몇 가지 고전적인 알고리즘에 대해 논의하고 퀵소트 알고리즘에 대한 대안을 홍보한다.
• 15 6분 내 정렬 알고리즘(Youtube) – 6분 내 15개 정렬 알고리즘의 시각화 및 "오디오빌레이션".
• OEIS 데이터베이스의 A036604 시퀀스 "정렬 번호: n개 요소를 정렬하는 데 필요한 최소 비교 횟수" – Ford-Johnson 알고리즘에 의해 수행됨.
• 명화에 사용된 분류 알고리즘 - 명화에 사용된 분류 알고리즘의 시각화
• 정렬 알고리즘 비교 - Python timeit과 Google Colab을 사용하여 9개의 주 정렬 알고리즘에 대한 일련의 테스트를 실행한다.