퀵 정렬(quick sort)
퀵 정렬(Quick Sort)은 "분할 정복" 알고리즘의 한 종류다. 퀵 정렬은 평균적으로 매우 효율적이며, 인플레이스 정렬 알고리즘 중 하나로, 추가 메모리를 거의 사용하지 않는다는 특징이 있다.
동작 원리
- 피벗 선택: 정렬할 배열이나 리스트에서 하나의 요소를 선택합니다. 이를 피벗이라 한다.
- 분할: 피벗을 기준으로 배열을 두 부분(피벗보다 작은 부분과 피벗보다 큰 부분)으로 분할한다.
- 재귀적 정렬: 두 부분 배열에 대해 재귀적으로 퀵 정렬을 적용한다.
- 합병 단계가 필요하지 않습니다. 퀵 정렬의 모든 동작은 분할 단계에서 이루어진다.
상세 동작 원리
- 피벗 선택
- 배열에서 하나의 요소를 선택하여 피벗으로 설정한다. 피벗의 선택 방법은 여러 가지가 있지만, 가장 간단한 방법은 배열의 첫 번째 요소나 마지막 요소, 중앙값 등을 사용하는 것이다.
- 분할(Partitioning)
- 피벗을 기준으로 배열을 두 부분으로 나눈다.
- 피벗보다 작은 요소들은 왼쪽 부분 배열로, 피벗보다 큰 요소들은 오른쪽 부분 배열로 옮긴다.
- 이 과정 후에 피벗은 배열에서 정확한 위치(즉, 피벗의 최종 위치)에 위치하게 된다.
- 재귀적 정렬:
- 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 재귀적으로 같은 정렬 과정을 적용한다.
- 배열의 크기가 0이나 1이 될 때까지 이 과정을 반복한다. 배열의 크기가 0이나 1인 경우, 배열은 이미 정렬된 것으로 간주하고 별도의 정렬 과정을 거치지 않는다.
상세 예제
입력 배열: [8, 3, 5, 4, 7, 6]
- 피벗 선택
- 첫 번째 요소인 8을 피벗으로 선택해본다.
- 분할
- 8을 기준으로 나머지 요소들을 스캔한다. 이 때, 8보다 작은 수는 왼쪽에, 큰 수는 오른쪽에 위치시키려고 한다.
- 시작 지점(3)은 8보다 작으므로 왼쪽에 그대로 둔다.
- 다음 숫자인 5도 8보다 작으므로 왼쪽에 둔다.
- 이와 같이 전체 리스트를 스캔하면, 8보다 작은 수들은 왼쪽에, 큰 수들은 오른쪽에 위치하게 된다.
- 결과:
[3, 5, 4, 7, 6] + [8] - 이 때, 피벗인 8은 이미 올바른 위치에 있다(이 배열에서 가장 큰 수이므로).
- 재귀적 정렬
- 이제 왼쪽 부분 배열
[3, 5, 4, 7, 6]을 다시 퀵 정렬로 정렬해야 한다.
- 이제 왼쪽 부분 배열
- 피벗 선택
- 첫 번째 요소인 3을 피벗으로 선택한다.
- 분할
- 3을 기준으로 나머지 요소들을 스캔한다.
- 5, 4, 7, 6 모두 3보다 크므로, 3은 왼쪽 끝에 그대로 남게 된다.
- 결과:
[3] + [5, 4, 7, 6]
- 재귀적 정렬
- 이제
[5, 4, 7, 6]부분 배열을 다시 퀵 정렬로 정렬해야 한다. - 위의 과정을 반복하여
[5, 4, 7, 6]배열도 정렬된다.
- 이제
- 최종 결과
[3, 4, 5, 6, 7, 8]
위의 과정을 통해 주어진 배열이 퀵 정렬로 정렬되었다. 분할을 통해 작은 부분 문제로 나눈 뒤, 이 작은 문제들을 풀면서 원래 문제를 해결하는 방식으로 작동한다.
알고리즘 성능
최선과 평균의 경우, 의 성능을 보여주지만, 최악의 경우의 성능을 보여준다.
최악의 경우는 이미 정렬된 배열에서 매번 가장 크거나 작은 요소를 피벗으로 선택했을 때 발생한다. 하지만 이러한 상황은 실제로는 드물게 발생하며, 평균적인 성능은 매우 좋다.
장점
- 평균적으로 매우 빠르다.
- 메모리 사용량이 적다.
단점
- 최악의 경우 시간 복잡도가 이다.
- 배열이나 리스트가 부분적으로 정렬된 경우에 비효율적일 수 있다.
예제 코드
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([3,6,8,10,1,2,1]))코드를 위한 연습
연습1. 리스트 슬라이싱
다음 리스트를 리스트 슬리이상(예 [:2])을 이용해서 세 개로 짤라서 각 리스트 변수에 넣고 출력해보기.
data_list = [1, 2, 3, 4, 5]
출력:
print (data1)[1, 2]
print (data2) 3
print (data3)[4, 5]
data_list = [1, 2, 3, 4, 5]
# 리스트 슬라이싱을 사용해 세 부분으로 나눈다.
data1 = data_list[:2]
data2 = data_list[2]
data3 = data_list[3:]
# 결과 출력
print(data1) # [1, 2]
print(data2) # 3
print(data3) # [4, 5]연습2. 리스트 정렬
다음 리스트를 맨 앞에 데이터를 기준으로 작은 데이터는 left 변수에, 그렇지 않은 데이터는 right 변수에 넣기
data_list = [4, 1, 2, 5, 7]
data_list = [4, 1, 2, 5, 7]
def list_sort(list_item):
first_value = list_item[0]
left_list = []
right_list = []
for i in list_item[1:]: # list는 range를 쓰면 오류가 난다.
if i > first_value:
right_list.append(i)
elif i < first_value:
left_list.append(i)
else:
pass
return left_list, right_list
left, right = list_sort(data_list)
print("Left:", left)
print("Right:", right)아래는 오른쪽, 왼쪽으로 정렬한 코드.
data_list = [4, 1, 2, 5, 7]
def list_sort(list_item):
first_value = list_item[0]
left_list = []
right_list = []
for i in list_item[1:]:
if i > first_value:
right_list.append(i)
elif i < first_value:
left_list.append(i)
else:
pass
first_value_list = [first_value]
return_list = left_list + first_value_list + right_list
return return_list
a = list_sort(data_list)
print(a)연습3. pivot
다음 리스트를 맨 앞에 데이터를 pivot 변수에 넣고, pivot 변수 값을 기준으로 작은 데이터는 left 변수에, 그렇지 않은 데이터는 right 변수에 넣기
data_list = [4, 1, 2, 5, 7]
def divide_list(list_item):
first_value = list_item[0]
left = []
right = []
for i in list_item[1:]:
if i < first_value:
left.append(i)
else:
right.append(i)
return left, right
left, right = divide_list(data_list)
print("Left:", left) # Left: [1, 2]
print("Right:", right) # Right: [5, 7]연습4. 임의의 list
data_list 가 임의 길이일 때 리스트를 맨 앞에 데이터를 기준으로 작은 데이터는 left 변수에, 그렇지 않은 데이터는 right 변수에 넣기
import random
data_list = random.sample(range(100), 10)
left = []
right = []
pivot = data_list[0]
for item in data_list[1:]:
if item < pivot:
left.append(item)
else:
right.append(item)
print("Data List:", data_list)
print("Pivot:", pivot)
print("Left:", left)
print("Right:", right)퀵 정렬 알고리즘
def quick_sort(arr):
# 리스트에 원소가 하나 이하라면 이미 정렬된 상태
if len(arr) <= 1:
return arr
pivot = arr[0] # 피벗 설정 (이 예에서는 맨 앞의 원소를 피벗으로 사용)
tail = arr[1:] # 피벗을 제외한 리스트
# 분할된 왼쪽 부분
left_side = [x for x in tail if x <= pivot]
# 분할된 오른쪽 부분
right_side = [x for x in tail if x > pivot]
# 왼쪽 부분과 오른쪽 부분을 각각 정렬한 뒤, 피벗과 합쳐서 반환
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
# 예제
arr = [3, 5, 8, 4, 9, 1, 6, 2, 7]
print(quick_sort(arr))알고리즘 설명
- 'left_side'는 'tail'에 있는 원소 중에서 피벗보다 작거나 같은 원소들만 모아 새로운 리스트 생성
- 'right_side'는 'tail'에 있는 원소 중에서 피벗보다 큰 원소들만 모아 새로운 리스트 생성
예를 들어,
pivot = 5
tail = [3, 7, 8, 4, 2]
이라고 하면:
left_side는 [3, 4, 2]
right_side는 [7, 8]
가 된다.
이런 방식으로 피벗을 중심으로 리스트를 두 부분으로 나누게 되며, 그 다음 각 부분에 대해 재귀적으로 퀵 정렬을 수행하게 된다.
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
- quick_sort(left_side)는 left_side 리스트에 대해 퀵 정렬을 수행하고 정렬된 결과를 반환한다. left_side에는 피벗보다 작은 값들이 포함되어 있다.
- quick_sort(right_side)는 right_side 리스트에 대해 퀵 정렬을 수행하고 정렬된 결과를 반환한다. right_side에는 피벗보다 큰 값들이 포함되어 있다.
이러한 방식으로 현재의 left_side와 right_side를 다시 퀵 정렬 함수에 넣어 정렬하는 과정이 재귀적으로 계속 이루어진다.
이 재귀 호출은 각 서브리스트의 크기가 1이하가 될 때 까지 계속되며, 크기가 1 이하의 서브리스트는 이미 정렬된 상태로 간주되어 그대로 반환된다.
리스트 컴프리핸션(List Comprehension)
# list comprehension 문법
# 가장 기본적인 형태
[expression for element in iterable]
# 조건문이 추가된 형태
[expression for element in iterable if condition]- 'expression': 새로운 리스트에 추가될 아이템
- 'element': 변수명
- 'old_list': 기존 리스트
- 'condition': 조건문 (해당 조건을 만족하는 원소만 새로운 리스트에 추가됨)
