정렬 알고리즘

컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 유용히 쓰인다.

버블 정렬은 1956년에 분석되었다.^[1] 수없이 많은 논의를 거쳐왔지만, 쓸만한 새로운 정렬 알고리즘들은 현재도 계속 발명되고 있다(예를 들어, 라이브러리 정렬은 2004년에 발표되었다). 정렬 알고리즘은 다양한 핵심 알고리즘 개념 — 점근 표기법, 분할 정복 알고리즘, 자료 구조, 최악의 경우, 평균적인 경우, 최선의 경우 등 — 을 소개하는 데 적당하기 때문에, 컴퓨터 과학 강의에서 입문 과정으로 유행하고 있다.

역사

컴퓨팅의 시작부터 정렬 알고리즘은 단순한 목표지만 효율적으로 실행하기 위해 상당한 연구가 진행되어 왔다. 1951년 즈음 초기 정렬 알고리즘 개발자들 가운데 에니악과 유니박을 작업하였던 베티 홀버튼(Betty Holberton)이 있었다.^[2]^[3] 거품 정렬이 1956년 초에 분석되었다.^[4] 비교 정렬 알고리즘은 Ω(n log n) 비교를 위한 중요한 요건이 있다. 계수 정렬 등 비교에 기반을 두지 않는 알고리즘은 더 나은 성능을 보일 수 있다. 점근 최적 알고리즘(Asymptotically optimal algorithm)들은 20세기 중순부터 알려졌다. 유용하고 새로운 알고리즘들은 여전히 발명되고 있으며 그 중 현재 널리 쓰이는 팀소트는 2002년으로 거슬러 올라가며 라이브러리 소트는 2006년 처음 출판되었다.

정렬 알고리즘은 컴퓨터 과학 소개 수업에서 일반적이며 여기서 문제를 위한 풍부한 알고리즘들은 점근 표기법, 분할 정복 알고리즘 등의 다양한 핵심 알고리즘 개념, 그리고 힙과 이진 트리 등의 자료 구조, 확률적 알고리즘, 최선, 최악, 그리고 평균의 경우 분석, 타임스페이스 트레이드오프, 하한 및 상한을 소개한다.

분류

정렬 알고리즘은 다음과 같은 기준으로 분류된다:

원소들의 크기 비교에 따른 계산 복잡도 (최선, 최악, 평균 동작). 직렬 정렬 알고리즘의 경우 최선 동작은 O(n log n), 최선 동작 중 병렬 정렬은 O(log² n), 최악 동작은 O(n²)이다. (점근 표기법 참고.) 직렬 정렬의 이상적인 동작은 O(n)이지만 평균 케이스에는 가능치 않다. 최적의 병렬 정렬은 O(log n)이다. 비교 기반 정렬 알고리즘은 대부분의 입력에 대해 최소 Ω(n log n)개의 비교가 필요하다.
원소들의 교환 횟수에 따른 계산 복잡도.
메모리 사용량 (및 다른 컴퓨터 자원의 사용량). 특히 일부 정렬 알고리즘들은 제자리(in-place, 인플레이스)이다. 정확히 말해 제자리 정렬은 정렬되는 항목 외에 O(1)개의 메모리만 필요하며 O(log(n))개의 추가적인 메모리를 인플레이스로 간주한다.
재귀. 일부 알고리즘들은 재귀성을 띄거나 재귀성을 띄지 않을 수 있으며 다른 알고리즘들은 그 둘의 특성을 지닐 수 있다. (예: 머지 소트)
안정성: 안정적인 정렬 알고리즘들은 동일 키(예: 값)의 레코드의 상대적인 순서를 관리한다.
비교 정렬인지 아닌지의 여부. 비교 정렬은 비교 연산자를 통해 2개의 요소만을 비교함으로써 데이터를 검사한다.
일반적인 방식: 삽입, 교환, 선택, 병합 등. 교환 정렬에는 거품 정렬과 퀵소트가 있다. 선택 정렬에는 셰이커 소트와 힙소트가 있다.
알고리즘이 직렬인지 정렬인지의 여부. 이 토론의 나머지 부분은 거의 예외적으로 직렬 알고리즘에 집중하며 직렬 조작을 다룬다.
순응성: 입력을 미리 정리하는 일이 실행 시간에 영향을 미치는지의 여부. 이를 고려사항에 넣는 알고리즘들은 순응적이다.

안정성

플레잉카드의 안정 정렬의 예. 안정 정렬로 순위별로 카드를 병렬할 때 5 두 장은 원래 위치했던 정렬된 결과와 같은 순서로 유지하여야 한다. 비안정 정렬로 정렬되는 경우 5는 정렬된 결과에서 반대 순서로 오게 될 수도 있다.

안정 정렬 알고리즘은 반복되는 요소를 입력 때와 동일한 순서로 정렬시킨다. 특정한 유형의 데이터를 정렬할 때 정렬 순서 결정 시 데이터의 일부분만 검사한다.

안정성은 몇 가지 이유로 중요하다. 예를 들어, 데이터가 학생 이름으로 우선 정렬되면(일부의 경우 웹 페이지에 동적으로) 데이터는 이제 어느 학급에 위치하는지에 따라 다시 정렬된다. 학생들이 같은 학급에 있다고 가정한다면 이들의 이름 순서는 특정한 순서가 아니게 뒤섞이며 이는 성가신 문제일 수 있다. 정렬 알고리즘이 안정적이면 학생 이름은 정상적인 순서에 위치할 수 있다.

알고리즘의 비교

아래 표에서 $n$ 은 정렬된 레코드의 수를 의미한다. "평균"과 "최악" 열은 각 키의 길이가 일정하고 모든 비교, 교환, 기타 필요한 조직이 일정한 시간에 수행될 수 있다는 가정 하의 각 케이스별 시간 복잡도를 나타낸다. "메모리"는 동일한 가정에서 리스트 그 자체에서 사용되는 것 이상으로 필요한 보조 기억공간의 양을 의미한다. 아래에 나열된 실행 시간과 메모리 요건은 점근 표기법 안에서 이해해야 하므로 로그 밑수(base of the logarithms)는 문제가 되지 않는다. $log 2 n$ 표기는 $(log n) 2$ 를 의미한다.

비교 정렬

다음은 비교 정렬 표이다. 비교 정렬은 $O (n log n)$ 보다 더 나은 성능을 낼 수 없다.^[5]

비교 정렬
이름	최선	평균	최악	메모리	안정	방식
퀵 정렬	$n\log n$ variation is $n$	$n\log n$	$n^{2}$	$\log n$ on average, worst case space complexity is $n$ ; Sedgewick variation is $\log n$ worst case.	일반적인 제자리 정렬은 안정적이지 못하다. 안정판이 존재한다.	파티셔닝
합병 정렬	$n\log n$	$n\log n$	$n\log n$	$n$ A hybrid block merge sort is O(1) mem.	예	합병
제자리 합병 정렬	—	—	$n\log ^{2}n$ 상단 참고. 하이브리드의 경우 $n\log n$	1	예	합병
힙 정렬	$n$ 모든 키가 구별되는 경우, $n\log n$	$n\log n$	$n\log n$	1	아니오	선택
삽입 정렬	$n$	$n^{2}$	$n^{2}$	1	예	삽입
인트로소트	$n\log n$	$n\log n$	$n\log n$	$\log n$	아니오	파티셔닝, 선택
선택 정렬	$n^{2}$	$n^{2}$	$n^{2}$	1	아니오	선택
팀소트	$n$	$n\log n$	$n\log n$	$n$	예	삽입, 합병
큐브소트	$n$	$n\log n$	$n\log n$	$n$	예	삽입
셸 정렬	$n\log n$	Depends on gap sequence	Depends on gap sequence; best known is $n^{1.25}$	1	아니오	삽입
거품 정렬	$n$	$n^{2}$	$n^{2}$	1	예	교환
이진 트리 정렬	$n\log n$	$n\log n$	$n\log n$ (balanced)	$n$	예	삽입
사이클 정렬	$n^{2}$	$n^{2}$	$n^{2}$	1	아니오	삽입
라이브러리 소트	$n$	$n\log n$	$n^{2}$	$n$	예	삽입
페이션스 소팅	$n$	—	$n\log n$	$n$	아니오	삽입, 선택
스무스소트	$n$	$n\log n$	$n\log n$	1	아니오	선택
스트랜드 소트	$n$	$n^{2}$	$n^{2}$	$n$	예	선택
토너먼트 정렬	$n\log n$	$n\log n$	$n\log n$	$n$ ^[6]	아니오	선택
칵테일 정렬	$n$	$n^{2}$	$n^{2}$	1	예	교환
빗질 정렬	$n\log n$	$n^{2}$	$n^{2}$	1	아니오	교환
그놈 정렬	$n$	$n^{2}$	$n^{2}$	1	예	교환
언셔플 소트^[7]	$n$	$kn$	$kn$	In-place for linked lists. n * en:sizeof(link) for array. n+1 for array?	아니오	분산, 합병
Franceschini's method^[8]	—	$n\log n$	$n\log n$	1	예	?
블록 정렬	$n$	$n\log n$	$n\log n$	1	예	삽입, 합병
홀짝 정렬	$n$	$n^{2}$	$n^{2}$	1	예	교환
커브 정렬	$n$	$n^{2}$	$n^{2}$	$\Omega (1)\cap {\mathcal {O}}(n)$	예	삽입, 계수

비교가 아닌 정렬

다음의 표는 정수 정렬 알고리즘들과 비교 정렬이 아닌 기타 정렬 알고리즘들을 기술한다. 그러므로 $Ω (n log n)$ 에 제한을 받지 않는다. 아래의 복잡도는 $n$ 개의 항목이 정렬될 것으로 간주되며 크기 $k$ 의 키, 숫자 크기 $d$ , 정렬될 수의 범위 $r$ 이 수반된다. 이 중 다수는 모든 항목들이 고유한 키 값을 지닐 수 있을 만큼 키의 크기가 충분히 크므로 $n ≪ 2 k$ 에서 ≪는 "훨씬 더 작은"을 의미한다. 단위 원가 랜덤 접근 기계 모델에서 기수 정렬과 같은 $\scriptstyle n\cdot {\frac {k}{d}}$ 의 실행 타임을 갖는 알고리즘들은 $Θ(n log n)$ 에 비례하는 시간이 소요되는데, 그 이유는 $n$ 이 $2^{\frac {k}{d}}$ 미만으로 제한되고 정렬 대상이 되는 상당수의 요소들이 메모리에 이들을 저장하기 위해 더 큰 $k$ 를 요구하기 때문이다.^[9]

비교가 아닌 정렬
이름	최선	평균	최악	메모리	안정	$n ≪ 2 k$
비둘기집 정렬	—	$n+2^{k}$	$n+2^{k}$	$2^{k}$	예	예
버킷 정렬 (uniform keys)	—	$n+k$	$n^{2}\cdot k$	$n\cdot k$	예	아니요
버킷 정렬 (integer keys)	—	$n+r$	$n+r$	$n+r$	예	예
계수 정렬	—	$n+r$	$n+r$	$n+r$	예	예
LSD 기수 정렬	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	예	아니요
MSD 기수 정렬	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	예	아니요
MSD 기수 정렬 (제자리)	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$2^{d}$	아니요	아니요
스프레드소트	$n$	$n\cdot {\frac {k}{d}}$	$n\cdot \left({{\frac {k}{s}}+d}\right)$	${\frac {k}{d}}\cdot 2^{d}$	아니요	아니요
버스트소트	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	아니요	아니요
플래시소트	$n$	$n+r$	$n^{2}$	$n$	아니요	아니요
포스트맨 정렬	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	—	아니요

샘플소트는 데이터를 여러 버킷으로 효율적으로 분배한 다음 여러 프로세서로 정렬을 전달시킴으로써 비교가 아닌 정렬을 병렬화하기 위해 사용할 수 있으며, 서로 간 버킷이 이미 정렬되어 있으므로 합병할 필요가 없다.

기타

일부 알고리즘들은 위에 논의된 것들에 비해 속도가 느린 편인데, 예를 들어 보고정렬과 같은 경우 한도가 없는 실행 시간을 지니고 꼭두각시 정렬은 O(n^2.7)의 실행 시간을 지닌다. 이 정렬들은 알고리즘의 실행 시간이 어떻게 예측되는지를 증명하기 위해 교육용으로 기술되는 것이 보통이다. 다음의 표는 매우 낮은 성능 또는 특수 하드웨어 요구사항으로 인해 전통적인 소프트웨어 환경에서 실제 사용에는 실용적이지 못한 일부 정렬 알고리즘들을 기술하고 있다.

이름	최선	평균	최악	메모리	안정	비교
주판 정렬	$n$	$S$	$S$	$n^{2}$	빈칸	아니요
단순 팬케이크 정렬	—	$n$	$n$	$\log n$	아니요	예
스파게티(폴) 정렬	$n$	$n$	$n$	$n^{2}$	예	폴링
정렬망	$\log ^{2}n$	$\log ^{2}n$	$\log ^{2}n$	$n\log ^{2}n$	다양함 (안정 정렬망은 더 많은 비교가 요구된다)	예
바이토닉 정렬	$\log ^{2}n$	$\log ^{2}n$	$\log ^{2}n$	$n\log ^{2}n$	아니요	예
보고정렬	$n$	$(n\times n!)$	$\infty$	1	아니요	예
꼭두각시 정렬	$n^{\log 3/\log 1.5}$	$n^{\log 3/\log 1.5}$	$n^{\log 3/\log 1.5}$	$n$	아니요	예

종류

정렬 알고리즘은 그 특징에 따라 몇 가지로 분류할 수 있다.

비교 정렬

비교 정렬은 원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘들을 일컫는다. 예를 들어 거품 정렬(bubble sort)은 비교하는 원소들이 숫자거나, 문자열이거나, 심지어는 복잡한 객체에 대해서도 순서가 결정되어 있다면 적용할 수 있다.

비교 정렬 알고리즘들은 아무리 빨라도 최악의 경우 $\Omega \left(n\log n\right)$ 시간을 필요로 한다. 이는 이 알고리즘들을 결정 트리의 형태로 기술할 수 있다는 점에서 증명할 수 있는데, $n$ 개의 원소들의 순열은 $n!$ 가지로 이들을 잎 노드로 가지는 결정 트리의 깊이는 스털링 근사에 따라 적어도 $\lceil \log n!\rceil \approx n\log n$ 이어야 하기 때문이다.

비교 정렬이 아닌 알고리즘들은 이런 시간 복잡도의 제약이 없지만, 대신 다른 제약을 가질 수 있다. 예를 들어 기수 정렬은 사전순으로 표기하고 분리하기 쉬운 숫자나 문자열에 대해서는 효과적이지만, 그렇지 않은 객체들에 대해서는 일반 비교 정렬보다 느릴 수 있다.

제자리 정렬

제자리 정렬은 원소들의 개에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘들을 의미하며, 제자리 알고리즘의 범위에 포함된다. 예를 들어 삽입 정렬은 이미 주어진 원소들을 옮긴 뒤 적절한 위치에 원소를 삽입하는 연산을 반복하는데, 이 과정에서 원소들을 담는 공간 외에 추가로 사용될 수 있는 공간은 옮겨지는 원소가 저장되는 공간과 루프 변수 정도에 불과하다.

퀵 정렬은 제자리 알고리즘의 정의에 따라서 제자리 정렬로 분류할 수도 있고 아닐 수도 있다. 퀵 정렬은 재귀적으로 정의되기 때문에 스택을 사용하게 되는데, 이 스택의 깊이는 $n$ 개의 원소에 대해 $\Omega \left(\log n\right)$ 에 비례하므로 전체 공간 복잡도는 상수가 아니다. 하지만 실용적인 의미에서 퀵 정렬은 상대적으로 작은 메모리만을 더 사용하기 때문에 흔히 제자리 정렬로 기술된다.

온라인 정렬

온라인 정렬은 모든 원소들이 처음부터 주어지지 않고 차례대로 들어 오는 경우도 처리할 수 있는 정렬 알고리즘을 의미하며, 온라인 알고리즘에 해당된다. 대표적으로 합병 정렬은 이미 정렬된 여러 개의 부분 리스트를 관리하다가 매 원소가 들어 올 때마다 적절한 리스트에 추가하고 필요하면 리스트들을 합병하는 식으로 온라인 정렬로 만들 수 있다.

저명한 정렬 알고리즘

정렬 알고리즘의 수는 많지만 실용적인 구현체의 경우 일부의 알고리즘들이 우위를 차지하고 있다. 작은 데이터 집합의 경우 삽입 정렬이 널리 사용되는 반면 큰 데이터 집합의 경우 점근적으로 효율적인 정렬이 사용되며 여기에는 주로 힙 정렬, 합병 정렬, 퀵 정렬이 있다. 효율적인 구현체들은 일반적으로 '정렬 전반을 위한 점진적으로 효율적인 알고리즘'을 '재귀 하한의 작은 리스트들을 위한 삽입 정렬'과 병합한 하이브리드 알고리즘을 사용한다. 상당한 튜닝을 거친 구현체들은 안드로이드, 자바, 파이썬에 쓰이는 팀소트(합병 정렬, 삽입 정렬, 추가 로직), 일부 C++ sort 구현체와 닷넷에 (여러 형태로) 쓰이는 인트로소트(퀵정렬과 힙 정렬) 등 더 복잡한 종류를 사용한다.

고정 간격의 숫자와 같은 더 제한된 데이터의 경우 계수 정렬이나 기수 정렬과 같은 분산 정렬이 널리 쓰인다. 거품 정렬과 같은 종류들은 실제로는 드물게 쓰이지만 교육 및 이론 토론에서 흔히 볼 수 있다.

물리적으로 객체를 정렬할 때(예: 논문, 테스트, 책을 알파벳 순으로 정리) 사람들은 작은 집합에 대해 직관적으로 삽입 정렬을 사용하는 것이 보통이다. 큰 집합의 경우 사람들은 보통 이니셜 문자와 같은 최초 버킷을 사용하며 매우 큰 집합의 경우 여러 버킷을 사용하는 것이 정렬에 실용적이다. 이를테면 객체들을 바닥 위나 넓은 공간 위에 퍼트려놓는다든 방식으로 공간이 상대적으로 저렴한 경우가 있는데, 이때 특히 객체를 먼 공간으로 움직이는 등의 조작에 대한 비용은 높아지게 되므로 참조의 지역성은 중요하다. 합병 정렬은 특히 두 손을 사용하는 등 물리적인 물체를 다루기 실용적인 반면 힙 정렬이나 퀵 정렬 등 다른 알고리즘들은 인간이 직접 사용하기에는 적절치 않다. 공간을 남기는 삽입 정렬의 변종인 라이브러리 소트 등의 다른 알고리즘들 또한 물리적 이용에 실용적이다.

단순 정렬

가장 단순한 정렬 중 삽입 정렬과 선택 정렬이 있으며 이 둘 모두 낮은 부하로 인해 작은 데이터에 효율적이지만 큰 데이터에는 효율적이지 않다. 삽입 정렬은 대부분 정렬된 데이터에 대해 비교를 덜 하고 성능이 좋은 이유로 일반적으로 선택 정렬보다 현실적으로 더 빠르기 때문에 선호되는 경향이 있으나 선택 정렬은 쓰기를 덜 하므로 쓰기 성능에 제약이 있는 환경에 사용된다.

삽입 정렬

삽입 정렬은 작은 리스트와 대부분 정렬된 리스트에 상대적으로 효율적인 단순한 정렬 알고리즘이며 더 복잡한 알고리즘의 일부분으로 사용되기도 한다. 리스트로부터 요소를 하나씩 취한 다음 마치 돈을 지갑에 넣는 방식과 비슷하게 이들을 올바른 위치에, 새로 정렬된 리스트에 삽입함으로써 동작한다.^[10] 배열의 경우 새 리스트와 남아있는 요소들은 배열 공간을 공유할 수 있으나 삽입의 경우 잇따르는 모든 요소를 하나씩 이동해야 하므로 비용이 많이 든다. 셸소트는 큰 리스트에 더 효율적인 삽입 정렬의 변종이다.

선택 정렬

선택 정렬은 제자리 비교 정렬이다. 복잡도는 O(n²)이므로 큰 리스트에는 비효율적이며, 유사한 삽입 정렬보다 성능이 더 떨어지는 것이 일반적이다. 선택 정렬은 단순함이 특징이며 특정한 상황에서는 더 복잡한 알고리즘보다 성능상 우위가 있다.

이 알고리즘은 최소값을 찾고 값을 최초 위치와 바꿔친 다음 리스트의 나머지 부분에 대해 이 과정을 반복한다.^[11] 교환 과정은 n개를 넘지 않으므로 교환 비용이 많이 드는 상황에서 유용하다.

효율적인 정렬

실용적인 일반 정렬 알고리즘들은 평균 시간 복잡도(및 일반적으로 최악의 경우의 복잡도) O(n log n)의 알고리즘에 기반한 경우가 대부분이며 그 중 가장 흔한 것이 힙 정렬, 합병 정렬, 퀵 정렬이다. 제각기 장단점이 있으며, 단순 합병 정렬의 구현체는 O(n) 추가 공간을 사용하며 단순한 퀵 정렬 구현체는 O(n²) 최악의 경우 복잡도를 사용하는 것이 가장 큰 특징이다. 이 문제들은 더 복잡한 알고리즘의 비용으로 해결되거나 개선할 수 있다.

이 알고리즘들이 다양한 수정이 수반되는 실생활 데이터를 기준으로 랜덤 데이터에 점근적으로 효율적이다. 첫째로, 이 알고리즘들이 일으키는 부하는 크기가 작은 데이터일수록 중대한 까닭에 하이브리드 알고리즘이 사용되기도 하며 데이터가 충분히 작으면 보통 삽입 정렬로 전환된다. 둘째로, 알고리즘은 이미 정렬된 데이터나 거의 정렬이 마무리된 데이터에 대해 성능이 떨어지는 경우가 있기 때문에 이 알고리즘들은 실생활 데이터에 일반화되어 있으며 대략적인 알고리즘들에 의해 O(n) 시간으로 정렬이 가능하다. 끝으로, 이 알고리즘들은 불안정 정렬에 속할 수 있는데 정렬 시 안정성은 바람직한 속성으로 간주되기도 한다. 그러므로 팀소트(합병 정렬 기반) 또는 인트로소트(퀵 정렬 기반으로, 필요 시 중간에 힙 정렬로 변경됨)와 같은 더 복잡한 알고리즘들이 적용되기도 한다.

합병 정렬

힙 정렬

퀵 정렬

셸 소트

거품 정렬 및 변종

버블 정렬

빗질 정렬

분산 정렬

계수 정렬

버킷 정렬

기수 정렬

같이 보기

검색 알고리즘

참조

↑ [1]
↑ “Meet the 'Refrigerator Ladies' Who Programmed the ENIAC”. 《Mental Floss》. 2013년 10월 13일. 2016년 6월 16일에 확인함.
↑ Lohr, Steve (2001년 12월 17일). “Frances E. Holberton, 84, Early Computer Programmer”. NYTimes. 2014년 12월 16일에 확인함.
↑ Demuth, H. Electronic Data Sorting. PhD thesis, Stanford University, 1956.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), 〈8〉, 《Introduction To Algorithms》 3판, Cambridge, MA: The MIT Press, 167쪽, ISBN 978-0-262-03293-3
↑ “보관된 사본” (PDF). 2022년 8월 23일에 원본 문서 (PDF)에서 보존된 문서. 2019년 11월 19일에 확인함.
↑ Kagel, Art (November 1985). “Unshuffle, Not Quite a Sort”. 《Computer Language》 2 (11).
↑ Franceschini, G. (June 2007). “Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves”. 《Theory of Computing Systems》 40 (4): 327–353. doi:10.1007/s00224-006-1311-1.
↑ Nilsson, Stefan (2000). “The Fastest Sorting Algorithm?”. 《닥터 돕스 저널》.
↑ Wirth, Niklaus (1986), 《Algorithms & Data Structures》, Upper Saddle River, NJ: Prentice-Hall, 76–77쪽, ISBN 978-0130220059
↑ Wirth 1986, 79–80쪽

추가 문헌

Knuth, Donald E. (1998), 《Sorting and Searching》, The Art of Computer Programming 3 2판, Boston: Addison-Wesley, ISBN 978-0201896855

외부 링크

위키미디어 공용에 관련된
미디어 분류가 있습니다.

정렬 알고리즘

Sorting Algorithm Animations - 웨이백 머신 (보관됨 3 3월 2015)
Sequential and parallel sorting algorithms Archived 2012년 12월 13일 - 웨이백 머신 – explanations and analyses of many sorting algorithms
Dictionary of Algorithms, Data Structures, and Problems – dictionary of algorithms, techniques, common functions, and problems
Slightly Skeptical View on Sorting Algorithms – Discusses several classic algorithms and promotes alternatives to the 퀵 정렬 algorithm
15 Sorting Algorithms in 6 Minutes (Youtube) – visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes
A036604 sequence in OEIS database titled "Sorting numbers: minimal number of comparisons needed to sort n elements" – which performed by en:Ford–Johnson algorithm
Sorting Algorithms Used on Famous Paintings (Youtube) - Visualization of Sorting Algorithms on Many Famous Paintings.

[1] [1]

[refrigerator-2] “Meet the 'Refrigerator Ladies' Who Programmed the ENIAC”. 《Mental Floss》. 2013년 10월 13일. 2016년 6월 16일에 확인함.

[NYTimes-3] Lohr, Steve (2001년 12월 17일). “Frances E. Holberton, 84, Early Computer Programmer”. NYTimes. 2014년 12월 16일에 확인함.

[4] Demuth, H. Electronic Data Sorting. PhD thesis, Stanford University, 1956.

[5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), 〈8〉, 《Introduction To Algorithms》 3판, Cambridge, MA: The MIT Press, 167쪽, ISBN 978-0-262-03293-3

[6] “보관된 사본” (PDF). 2022년 8월 23일에 원본 문서 (PDF)에서 보존된 문서. 2019년 11월 19일에 확인함.

[7] Kagel, Art (November 1985). “Unshuffle, Not Quite a Sort”. 《Computer Language》 2 (11).

[8] Franceschini, G. (June 2007). “Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves”. 《Theory of Computing Systems》 40 (4): 327–353. doi:10.1007/s00224-006-1311-1.

[9] Nilsson, Stefan (2000). “The Fastest Sorting Algorithm?”. 《닥터 돕스 저널》.

[10] Wirth, Niklaus (1986), 《Algorithms & Data Structures》, Upper Saddle River, NJ: Prentice-Hall, 76–77쪽, ISBN 978-0130220059

[11] Wirth 1986, 79–80쪽

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]