퀵정렬

범용기술 : 다양한 기술을 통해 해결 방법을 알아내는것

분할정복 ( 범용기술 중 하나 )

문제를 더 작은 조각으로 나누어 푼다. '기본단계'까지

퀵정렬 ( 분할정복전략사용 )

def quicksort(array):

if len(array) < 2: #기본단계

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)

기준 원소를 무작위로 선택한다. 평균 실행시간은 O(n log n), 최악의 경우 O(n²)

리스트에서 가장 큰 수를 찾기

def max (list):

if len(list) == 2:

return list[0] if list[0]>list[1] else list[1]

sub_max = max(list[1:])

return list[0] if list[0]>sub_max else sub_max