정렬 알고리즘

인접한 요소를 반복적으로 비교하고 순서가 잘못된 경우 교환하는 가장 기본적인 정렬 알고리즘입니다. 거품이 수면으로 떠오르듯이 큰 값이 점차 배열의 끝으로 이동합니다. 작은 데이터셋이나 정렬의 기본 원리를 이해하기 위한 교육 목적에 가장 적합합니다.

가장 작은 요소를 찾아 반복적으로 앞으로 이동시킵니다. 각 반복마다 남은 요소 중에서 최소값을 "선택"하고 정렬된 부분 뒤에 배치합니다. 최소한의 메모리 사용으로 구현이 간단하지만 입력에 관계없이 항상 O(n²) 시간이 걸립니다.

피벗 요소를 선택하고 배열을 왼쪽에는 작은 값, 오른쪽에는 큰 값으로 분할하는 매우 효율적인 정렬 알고리즘입니다. 평균 O(n log n) 시간 복잡도를 가지며 실제로 가장 널리 사용되는 정렬 방법입니다. 대부분의 프로그래밍 언어에서 내장 정렬 함수의 기초를 형성합니다.

먼저 최대 힙을 구축한 다음 루트 요소를 반복적으로 추출하여 정렬하는 이진 힙 데이터 구조를 사용합니다. 추가 메모리 없이 모든 경우에 O(n log n) 시간 복잡도를 보장합니다. 우선순위 큐 구현의 기초로도 사용됩니다.

각 요소의 발생 횟수를 세고 산술 연산을 통해 위치를 결정하는 비비교 정렬 알고리즘입니다. k가 입력 값의 범위일 때 O(n+k) 시간 복잡도를 달성합니다. 알려진 제한된 범위 내의 정수 정렬에 이상적입니다. 기수 정렬의 기초가 됩니다.

최하위 자릿수부터 최상위 자릿수까지 자릿수별로 요소를 처리하는 비비교 정렬 알고리즘입니다. 각 자릿수 위치에서 계수 정렬을 서브루틴으로 사용합니다. d가 자릿수일 때 O(d(n+k)) 시간을 달성합니다. 정수나 고정 길이 문자열 정렬에 탁월합니다.

멀리 떨어진 요소의 교환을 허용하는 삽입 정렬의 최적화입니다. 1로 감소하는 간격 시퀀스를 사용하여 요소를 최종 위치에 더 빠르게 이동시킵니다. 1959년 Donald Shell이 발명한 알고리즘의 이름을 따서 명명되었습니다.

요소를 여러 버킷에 분배하는 분포 기반 정렬 알고리즘입니다. 각 버킷은 다른 정렬 알고리즘을 사용하여 개별적으로 정렬됩니다. 입력이 범위에 걸쳐 균일하게 분포되어 있을 때 가장 잘 작동합니다. 평균 시간 복잡도는 O(n+k)입니다.

배열을 반으로 나누고, 각 절반을 재귀적으로 정렬한 다음, 다시 병합하는 분할 정복 알고리즘입니다. O(n log n) 시간을 보장하고 안정적이지만 추가 메모리가 필요합니다. 큰 데이터셋과 연결 리스트 정렬에 특히 효과적입니다.

손에 있는 카드를 정렬하는 것처럼 작동합니다 - 각 요소를 한 번에 하나씩 적절한 위치에 삽입합니다. 이미 정렬된 데이터에 대해 O(n) 시간에 실행되므로 작은 배열이나 거의 정렬된 데이터셋에 매우 효율적입니다. 간단하면서도 적응형 알고리즘입니다.

1.3 배수로 줄어드는 더 큰 간격으로 요소를 비교하여 배열 끝의 작은 값("거북이")을 제거하는 버블 정렬의 개선입니다. 간단한 수정으로 성능을 O(n²)에서 실제로 O(n²/2^p)로 극적으로 개선합니다. 작은 알고리즘 조정이 어떻게 상당한 개선을 가져올 수 있는지 보여줍니다.

개념적으로 가장 간단한 정렬 알고리즘 - 요소가 순서대로 있을 때는 앞으로 이동하고, 그렇지 않으면 교환하고 뒤로 이동합니다. 꽃병을 정렬하는 네덜란드 정원 놈의 이름을 따서 명명되었습니다. 삽입 정렬과 유사하지만 구현이 더 간단합니다. O(n²) 복잡도에도 불구하고 정렬 메커니즘을 이해하는 데 교육적 가치가 있습니다.