[알고리즘] 2750번 - 수 정렬하기 1번, 퀵 정렬(divide and conquer), python (2)

[백준 알고리즘] 2750번

정말 많은 정렬 알고리즘이 존재하고, 이번에 공부한 것은 퀵 정렬

 

1. list를 input으로 하면 맨 끝의 값을 pivot으로 선언

2. pivot을 기준으로 작으면 왼쪽, 크면 오른쪽으로 쌓기 (단 왼쪽 블럭과 오른쪽 블록이 정렬된 것은 아님)

3. 왼쪽 블록의 가장 오른쪽 값을 새로운 pivot으로 선언

4. 반복하기

 

 

2번 항목 상세

2번을 위해서 요소의 위치를 바꿔주는 함수, 반복하는 함수 partition함수 선언

 

# 두 요소의 위치를 바꿔주는 함수
def swap_elements(my_list, index1, index2):
    # 코드를 작성하세요.
    index_value1 = my_list[index1]
    index_value2 = my_list[index2]
    
    my_list[index1]  = index_value2
    my_list[index2]  = index_value1
    
    return my_list

# partition 함수
def partition(my_list, start, end):

    store_index = start
    for i in range(start, end):
        if my_list[i] < my_list[end]:
            swap_elements(my_list,i,store_index)
            store_index += 1
    swap_elements(my_list,store_index, end)
    return store_index

 

 

3번을 위한 최종 quicksort함수 선언

# 퀵 정렬
def quicksort(my_list, start=None, end=None ):

    if start == None and end == None:
        start = 0
        end = len(my_list) - 1
        
    if end - start < 1:
        return
    
    new_pivot=partition(my_list, start, end)            
    quicksort(my_list, start, new_pivot-1)
    quicksort(my_list, new_pivot+1, end)