5) Divide and Conquer 방식으로 퀵정렬을 해보자

 

5. Divide and Conquer 방식으로 퀵정렬을 해보자

# (1) 풀이

def swap_elements(my_list, index1, index2):
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]
    return my_list


# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의
    i = start
    b = start
    pivot = my_list[end]

    # 범위안의 모든 값들을 볼 때까지 반복문을 돌린다
    while i < end:
        # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다
        if my_list[i] <= pivot:
            swap_elements(my_list, i, b)
            b += 1
        i += 1
    swap_elements(my_list, end, b)

    return b


# 퀵 정렬
def quicksort(my_list, start, end):
    if end - start < 1:
        return
    mid = partition(my_list, start, end)
    quicksort(my_list, start, mid - 1)
    quicksort(my_list, mid + 1, end)

 

 

# (2) 1번의 퀵 함수 가공

def swap_elements(my_list, index1, index2):
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]
    return my_list


# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의
    i = start
    b = start
    pivot = my_list[end]

    # 범위안의 모든 값들을 볼 때까지 반복문을 돌린다
    while i < end:
        # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다
        if my_list[i] <= pivot:
            swap_elements(my_list, i, b)
            b += 1
        i += 1
    swap_elements(my_list, end, b)

    return b


# 퀵 정렬
def quicksort(my_list, start =0, end=None):
    if end == None:
        end = len(my_list)-1
    if end - start < 1:
        return
    mid = partition(my_list, start, end)
    quicksort(my_list, start, mid - 1)
    quicksort(my_list, mid + 1, end)

# 테스트 1
list1 = [1, 3, 5, 7, 9, 11, 13, 11]
quicksort(list1) # start, end 파라미터 없이 호출
print(list1)

# 테스트 2
list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
quicksort(list2) # start, end 파라미터 없이 호출
print(list2)

# 테스트 3
list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]
quicksort(list3) # start, end 파라미터 없이 호출
print(list3)

# 결과
[1, 3, 5, 7, 9, 11, 11, 13]
[1, 5, 7, 9, 13, 15, 28, 30, 48]
[1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]