이 글에서는 칵테일 정렬(Cocktail Sort) 알고리즘을 파이썬으로 구현하는 방법을 단계별로 살펴보겠습니다.
문제 정의
문제 — 주어진 리스트에 대해 칵테일 정렬을 수행하고, 정렬된 결과를 출력해야 합니다.
칵테일 정렬이란? — 칵테일 정렬은 버블 정렬(Bubble Sort)의 변형된 형태로, 한 번의 순회에서 양방향(왼쪽→오른쪽, 오른쪽→왼쪽)으로 번갈아 가며 탐색한다는 점이 특징입니다. 이를 통해 버블 정렬의 '거북이 문제'(작은 값이 배열 앞쪽으로 느리게 이동하는 현상)를 완화할 수 있습니다.
알고리즘 동작 원리
칵테일 정렬은 다음과 같은 과정으로 진행됩니다.
1. 정방향 순회 (왼쪽 → 오른쪽): 배열을 처음부터 끝까지 순회하면서 인접한 두 요소를 비교하고, 조건에 따라 값을 교환합니다. 이 과정이 끝나면 가장 큰 값이 배열의 맨 끝에 위치하게 됩니다.
2. 역방향 순회 (오른쪽 → 왼쪽): 이번에는 반대 방향으로 배열을 순회하며 인접 요소를 비교하고 교환합니다. 이 과정에서 가장 작은 값이 배열의 맨 앞으로 이동합니다.
3. 범위 축소 및 반복: 이미 정렬이 완료된 양 끝의 요소는 제외하고, 교환이 더 이상 발생하지 않을 때까지 위 과정을 반복합니다.
구현 예제
# 칵테일 정렬 함수
def cocktailSort(a):
n = len(a)
flag = True
start = 0
end = n - 1
while (flag == True):
# 이전 반복의 결과를 무시하기 위해 플래그 초기화
flag = False
# 왼쪽에서 오른쪽으로 순회
for i in range(start, end):
if (a[i] > a[i+1]):
a[i], a[i+1] = a[i+1], a[i]
flag = True
# 교환이 발생하지 않았다면 배열은 이미 정렬된 상태
if (flag == False):
break
# 플래그 초기화
flag = False
# 마지막 요소는 이미 정렬되었으므로 범위 축소
end = end - 1
# 오른쪽에서 왼쪽으로 순회
for i in range(end - 1, start - 1, -1):
if (a[i] > a[i+1]):
a[i], a[i+1] = a[i+1], a[i]
flag = True
# 첫 번째 요소도 정렬 완료
start = start + 1
# 메인 실행부
a = [2, 5, 4, 3, 8, 3, 4, 6]
cocktailSort(a)
print("Sorted array is:")
for i in range(len(a)):
print(a[i], end=" ")실행 결과
Sorted array is: 2 3 3 4 4 5 6 8
위 코드에서 사용된 모든 변수(n, flag, start, end)는 함수 내 지역 스코프(local scope)에 선언되며, 각 변수는 정렬 범위와 교환 여부를 추적하는 역할을 합니다. 특히 start와 end가 매 반복마다 조정되면서 이미 정렬된 영역을 건너뛰게 되어 불필요한 비교 연산을 줄일 수 있습니다.
시간 복잡도
칵테일 정렬의 시간 복잡도는 최악 및 평균 경우 O(n²), 최선의 경우(이미 정렬된 배열) O(n)입니다. 공간 복잡도는 제자리(in-place) 정렬 방식이므로 O(1)입니다.
결론
이 글에서는 파이썬으로 칵테일 정렬 프로그램을 구현하는 방법을 알아보았습니다. 칵테일 정렬은 버블 정렬보다 양방향 순회를 통해 다소 개선된 성능을 보이지만, 여전히 대규모 데이터에는 부적합하며 주로 학습 목적으로 활용됩니다.