CH 04. 퀵 정렬
- 분할 정복 전략
① 여러 작은 단계로 분할
② 작은 단계 해결
# 분할 정복
def sum(arr):
total = 0
for x in arr:
total += x
return total
print(sum([1, 2, 3, 4]))
** 유클리드 호제법 : 최대공약수 찾기 알고리즘
- 퀵 정렬 : 기준 원소를 기준으로 모든 원소를 기준 원소보다 큰지 작은지 분류
> 하위 배열이 정렬된 경우 : 왼쪽 배열 + 기준 원소 + 오른쪽 배열
> 하위 배열이 정렬되지 않은 경우 : 왼쪽, 오른쪽 배열에 각각 퀵 정렬 호출
> 최악의 경우 O(n) : 정렬된 배열에 항상 첫번째 원소를 기준 원소로 선택
> 최선의 경우 O(log n) : 정가운데 원소를 기준 원소로 선택
# 퀵 정렬
def quicksort(array):
if len(array) < 2: #원소값 1이면 그대로 출력
return array
else:
pivot = array[0] # 기준 원소
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
quicksort([15, 10]) + [33] + quicksort([])참고자료
Hello Coding 그림으로 개념을 이해하는 알고리즘
