퀵정렬

퀵정렬은 분할정복전략이다.

배열이 비어있거나 원소가 하나인 배열은 정렬할 필요가 없다.

def quicksort(array):
    if len(array) < 2:
        return array

원소가 2개이면 ex) 40 10 -> 10 40

첫번째 원소와 두번째 원소를 비교해 교환한다.

원소가 3개이면  

ex) 40 20 10 

배열에서 원소 하나를 고른다. 고른원소는 기준원소(pivot)라고 한다.

( 40 pivot 지정 )

기준원소(pivot)를 기준으로 기준원소보다 작은원소와 큰원소를 분류한다.

( 40보다 작으므로 왼쪽으로 분류 20 10 40 )

기준원소보다 작은숫자로 이루어진 하위배열 [20, 10]

기준원소 [40]

기준원소보다 큰 숫자들로 이루어진 하위배열 []

1. 기준원소 고른다.

2. 배열을 기준 원소보다 작은원소의 배열과 기준원소보다 큰 원소의 배열 두개의 하위배열로 분할

3. 하위배열에 대해 재귀적으로 퀵정렬 호출

1. 퀵정렬 소스코드

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]                                # pivot = 10, pivot = 5, pivot = 2
        less = [i for i in array[1:] if i<= pivot]      # less=[5,2,3], less=[2,3], less=[]
        greater = [i for i in array[1:] if i> pivot]    # greater=[], greater=[], greater=[3]
        return quicksort(less) + [pivot] + quicksort(greater)
 
        # [ 5,2,3 ] + [10] + [ ]
        # [ 2,3 ] + [5] + [ ]
        # [ ] + [2] + [ 3 ]
 
        # ([2]+[3]) = [2,3]
        # ([2,3] +[5]) = ([2]+[3])+[5] = [2]+[3]+[5]
        # [5,2,3] = ([2,3]+[5])+[10]  = [2]+[3]+[5]+[10]
        
print (quicksort([10,5,2,3]))

작업파일

quickSort.pptx

quickSort.py