All
정렬
주어진 데이터를 값의 크기 순서에 따라 재배치 하는것 (오름/내림차순)
내부 정렬
•
정렬한 전체 데이터를 주기억장치에 저장한 후 정렬하는 방식
비교기반 | 데이터 분포 기반 |
두 데이터 값 전체를 비교해 어떤값이 큰지 작은지 결정하여 정렬 | 데이터의 분포 정보를 활용해 정렬 |
선택, 버블, 삽입, 셸, 합병, 퀵, 힙 정렬 | 계수, 기수, 버킷 |
안정적 Stable 정렬
•
같은 값을 갖는 데이터에 대한 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식
•
입력
◦
5 1 2 3 6 2 4
•
정렬 후
◦
1 2 2 3 4 5 6 (안정)
◦
1 2 2 3 4 5 6 (불안정)
제자리 정렬 in-place
•
입력 배열 이외에 별도로 필요한 저장 공간이 상수 개를 넘지 않는 정렬
•
입력 크기 n이 증가해도 추가적인 저장 공간 사용하지 않음
선택 정렬 (Selection Sort)
전체 배열에서 가장 작은(또는 가장 큰) 값을 찾아 맨 앞의 값과 교환하는 방식으로 정렬함. 다음에는 두 번째 작은 값을 찾아 두 번째 위치와 교환하며 반복함.
1.
배열에서 가장 작은 원소를 선택한다.
2.
선택한 원소를 배열의 맨 앞과 교환한다.
3.
맨 앞을 제외한 나머지 배열에서 다시 가장 작은 원소를 선택하여 두 번째 위치와 교환한다.
4.
위 과정을 배열 전체가 정렬될 때까지 반복한다.
성능과 특징
•
입력 데이터의 순서에 민감하지 않음: 미정렬 부분에서 항상 (n-1) - i 번 비교 필요하므로 성능이 일정
•
시간 복잡도: 최선, 평균, 최악의 경우 모두 O(n2)
•
제자리 정렬
•
불안정 정렬
◦
1 2 4 4 3 > 1 2 3 4 4
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
Python
복사
버블 정렬 (Bubble Sort)
인접한 두 원소를 비교하여 큰 값(또는 작은 값)을 오른쪽(또는 왼쪽)으로 이동시키면서 정렬함. 매 패스를 수행할 때마다 가장 큰 값이 맨 뒤에 확정됨.
1.
인접한 두 원소를 비교하여 큰 값을 뒤로 이동시킨다.
2.
배열의 끝까지 반복하여 가장 큰 값을 배열의 마지막에 위치시킨다.
3.
다음 패스에서는 이미 정렬된 마지막 값을 제외하고 다시 비교하여 정렬한다.
개선된 버블 정렬
•
한 번의 패스 동안 교환이 한 번도 일어나지 않았다면 이미 정렬된 상태이므로 추가적인 패스를 중지할 수 있음.
성능과 특징
•
최선의 경우 (이미 정렬된 경우) O(n)
•
평균 및 최악의 경우 O(n2)
•
안정적 정렬
•
제자리 정렬
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
Python
복사
삽입 정렬 (Insertion Sort)
배열을 정렬된 부분과 미정렬 부분으로 나누고, 미정렬 부분에서 데이터를 하나씩 꺼내어 정렬된 부분에서 적절한 위치를 찾아 삽입함.
1.
정렬된 부분과 미정렬 부분으로 나눈다.
2.
미정렬 부분의 첫 번째 데이터를 선택한다.
3.
선택한 데이터를 정렬된 부분에서 적절한 위치에 삽입한다.
4.
위 과정을 반복하여 배열 전체를 정렬한다.
성능과 특징
•
최선의 경우 (거의 정렬된 경우) O(n)
•
평균 및 최악의 경우 O(n2)
•
안정적 정렬
•
제자리 정렬
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
Python
복사
셸 정렬 (Shell Sort)
삽입 정렬의 단점을 개선한 알고리즘으로, 멀리 떨어져 있는 원소를 비교하고 교환하여 한 번에 먼 거리를 이동시키는 방식으로 정렬함. 점점 간격(gap)을 줄여가며 삽입 정렬을 수행하는 방식
1.
적절한 간격(gap)을 선택한다.
2.
선택된 간격만큼 떨어져 있는 원소들을 비교하여 교환한다.
3.
간격을 점점 줄이며 위 과정을 반복한다.
4.
간격이 1이 될 때까지 반복하면 마지막 단계는 일반 삽입 정렬과 같아짐.
성능과 특징
•
삽입 정렬보다 성능이 크게 향상됨
•
시간 복잡도는 gap(간격)의 크기 및 감소 방식에 따라 달라짐 (평균 ~ O(1.25) ~ O(1.5))
•
일반적으로 불안정 정렬
•
제자리 정렬
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
Python
복사