#퀵정렬 #Quick_sort_1단계 #Divide하기

 

퀵 정렬의 핵심 아이디어?

파티션(partition)이란 리스트를 나누는 것을 의미한다. 퀵 정렬을 리스트에 있는 특정값을 기준으로 좌, 우 파티션 한다.

이후 좌, 우에 놓인 값들을 각각 정렬하여 합치게 되면 전체적으로 정렬이 된 리스트를 얻을 수 있다. 이 방식을 재귀적으로 적용한다. 즉, 좌, 우로 나뉜 부분들을 더 이상 나눌 수 없을 때까지 나눈다. 어떤 값 기준으로 나누고자할 때, 나누고자 하는 부분의 개수가 1개일 때 더이상 나눌 수 없는 상태가 된다. 

퀵 정렬에서 가장 어려운 것이 파티션부분(Divide)이다. 리스트에서 나눠야할 그룹에 속한 숫자들을 차례로 기준점(pivot)과 비교하면서 작으면 작은 그룹에, 크면 큰 그룹에 넣도록한다. 이 때, 각 그룹에 속한 숫자들은 정렬되어 있지 않다. 

이를 직접 구현하는 함수를 Divide함수라고 생각해보자. Divide 함수의 인자는 list, start_index, end_index를 받는다. 

def divide(list, start_index, end_index):

리스트의 숫자들을 차례대로 훑으면서, pivot보다 높은 값은 pivot보다 오른쪽에 위치하도록 해야 하는데 이때 필요한 것이 index를 통해서 숫자들을 옮긴다. 나는 이 문제를 처음 보았을 때, small, big 리스트를 따로 만들어서 차례대로 훑으면서 해당하는 그룹에 append()하도록 하였는데 이 경우 리스트가 굉장히 클 경우 소요되는 시간이 O(n)이 되기 때문에 옳게 풀은 것이 아니었다.

pivot보다 높은 값이 위치하는 인덱스를 알고, 아직 훑지 않은 리스트 부분을 가리키는 곳이 i라고 할 때 

i = start_index
b = start_index
p = end #pivot부분 len(my_list)-1로 표현된다. 

우리가 훑으려는 리스트의 부분의 index가 pivot의 인덱스(p)와 같이 않아지는 지점, 즉 적을 때까지 계속 이러한 작업을 반복해야 한다.

while i < p:
	if my_list[i] <= my_list[p]:
       swap_elements(my_list, i, b) #i의 요소와 b의 요소를 바꾼다.
       b += 1
    i +=1 #리스트를 훑어가면서 봐야 하므로, 1계속 증가시켜야 한다.

마지막으로, while문을 다 끝마쳤을 때다. 이 경우 기준이 되는 pivot값이 small과 big 사이에 놓이도록 해야 한다. 이는 big 그룹이 시작되는 인덱스(b)를 이용하여, 마지막 pivot이 위치한 요소값과 바꾼다. 

	swap_elements(my_list, b, p)
    p = b
    
    return b

 

#도움이 되셨다면? 공감버튼 꾹 눌러주는 센스 고고링?

#읽어주셔서 감사합니다.