알고리즘 이론
정렬이론-1

알고리즘

퀵 정렬(quick sort)

divide and conquer 과정을 사용 하는 정렬은 '합병 정렬' 말고도 퀵 정렬이라고 있다.

퀵정렬은 하나의 기준점을 정한 뒤, 기준 왼쪽은 기준 보다 작은 값 오른쪽은 많은 값을 정렬한 뒤 또 그 값 에서 기준을 정하는 과정을 반복해서 이루어 진다.

퀵 정렬은 그 리스트를 재구성 하는 것이기 때문에 상대적으로 combine 과정이 없고 divide 과정이 매우 중요하고 어렵다. 이 과정을 'partition'이라고 한다.

partition 함수 구현

1. 두 요소의 위치를 바꿔 주는 함수

def swap_elements(my_list, index1, index2):
    temp = my_list[index1]                  -> index1의 값을 임시값에 넣어준다.
    my_list[index1] = my_list[index2]       -> index2의 값을 index1에 넣어주고
    my_list[index2] = temp                  -> index2에 임시값에 저장된 index1값 넣어준다.

2. 퀵 정렬에서 사용되는 partition 함수

def partition(my_list, start, end):
    p = my_list end 값
    i = start 값
    b = big club의 값, start 값
    
    while i < p:
        if my_list[i] < my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
        i += 1
    
    swap_elements(my_lsit, b, p)       -> 마지막으로 p와 b를 교환해줘야지 pivot(기준)을 중간으로 정렬됨
    p = b
    
    return p

3. 퀵 정렬 구현하기

def quick_sort(my_list, start = 0, end = None):
    
    if end == None:
        end = len(my_list) - 1
    
    if end - start < 1:      -> base case 리스트가 한개 이하일때 정렬 없이 바로 나옴
        return               -> 리턴 값이 없음
        
    pivot = partiton(my_list, start, end)    -> 퀵정렬시 기준이 되는 pivot설정
    
    # pivot 왼쪽값 정렬
    quick_sort(my_list, start, pivot - 1)
    
    # pivot 오른쪽값 정렬
    quick_sort(my_list, pivot + 1, end)
    
    

출처 - codeit(알고리즘)