[알고리즘 일기] 16. 퀵 정렬(3)

문제 16. (2021-05-16)

 

퀵 정렬(3)

이전에 작성한 quicksort 함수를 파라미터 하나만을 이용해서 작성하시오.

 

 

❧ Before

# Test
test_list = [9, 5, 1, 5, 2, 8, 2, 7, 1, 3, 6, 2, 4, 7, 10, 11, 4, 6]
quicksort(test_list, 0, len(test_list) - 1)
print(test_list)

 

❧ After

# Test
test_list = [9, 5, 1, 5, 2, 8, 2, 7, 1, 3, 6, 2, 4, 7, 10, 11, 4, 6]
quicksort(test_list) # start, end 파라미터 없이 호출
print(test_list)

 

---

❧ 정답

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


def partition(my_list, start, end):
    b = 0 
    i = 0 
    p = end # pivot

    for i in range(0, p):
        if my_list[p] < my_list[i]:
            continue
        else:
            swap_elements(my_list, b, i)
            b += 1
            i += 1

    swap_elements(my_list, b, p)
    return b


# 퀵 정렬
def quicksort(my_list, start, end):
    merge_index = 0
    merge_index = partition(my_list,start,end)

    if merge_index == start:
        return my_list

    quicksort(my_list,0,merge_index-1 ) # 왼쪽 quicksort
    quicksort(my_list,merge_index,end) # 오른쪽 quicksort

 

728x90