정렬 알고리즘

정렬 알고리즘은 데이터를 정렬할 때 시간 복잡도, 공간 복잡도, 안정성, 성능 등을 고려하여 상황에 맞는 방식을 선택하며, 안정성에 따라 동일 값의 순서가 유지되는지 여부가 달라집니다.

빅-오 표기법은 알고리즘의 성능을 나타내며, 최악, 최선, 평균 케이스를 각각 O, Ω, θ로 표현하고, 항의 영향력을 무시하는 규칙을 기반으로 다양한 시간 복잡도를 설명한다.

순차정렬은 배열의 앞에서부터 최솟값을 찾아 교환하며 정렬하는 불안정한 알고리즘으로, 시간 복잡도는 최선과 최악 모두 O(n²)입니다.

버블정렬은 인접한 원소들을 비교하고 교환하여 뒤에서부터 정렬하는 안정적인 알고리즘으로, 시간 복잡도는 최선과 최악 모두 O(n²)입니다.

선택정렬은 배열에서 최솟값을 찾아 교환하며 정렬하는 불안정한 알고리즘으로, 시간 복잡도는 최선과 최악 모두 O(n²)입니다.

삽입정렬은 점진적으로 범위를 늘려가며 정렬하고, 배열이 어느 정도 정렬된 경우 효율적이나, 시간 복잡도는 최선 O(n), 최악 O(n²)이며 안정적인 정렬 알고리즘입니다.

쉘정렬은 삽입정렬을 간격을 두고 수행하여 점진적으로 정렬을 개선하는 알고리즘으로, 최선은 O(n), 평균은 O(n^1.5), 최악은 O(n²)이며 불안정합니다.

퀵정렬은 피벗을 기준으로 배열을 분할하고 재귀적으로 정렬하는 알고리즘으로, 평균적으로 빠르지만 피벗 선택이 부적절하면 최악의 시간복잡도를 가질 수 있습니다.

병합정렬은 배열을 재귀적으로 분할한 후 정렬하여 병합하는 안정적인 정렬 알고리즘으로, 항상 O(n log n)의 시간복잡도를 가집니다.

힙정렬은 힙 트리를 이용해 배열을 정렬하는 알고리즘으로, 항상 O(n log n)의 시간복잡도를 가지며 추가 메모리를 사용하지 않습니다.

기수정렬은 자릿수별로 배열을 정렬하는 알고리즘으로, 안정적이고 효율적인 시간복잡도 O(n)을 가지만 추가 메모리와 특정 조건 하에서만 사용 가능합니다.

계수정렬은 데이터의 빈도수를 기반으로 정렬하는 알고리즘으로, 효율적인 시간복잡도 O(n)을 가지지만, 큰 범위의 값에 대해 메모리 공간을 많이 차지할 수 있습니다.