[ Python_알고리즘 ] 분할정복법 ② 퀵 정렬

[ 퀵 정렬 ]

 

Pivot을 기준으로 Pivot 보다 작은 값들을 왼쪽으로, Pivot 보다 큰 값들은 오른쪽으로 정렬

 

Pivot을 기준으로 값들을 새롭게 배치

 

왼쪽에 있는 값들은 오른쪽에 있는 값들 보다 작기 때문에 크기 비교없이 각각 정렬해주면 전체 리스트가 정렬됨

 

def swap_elements(my_list, index1, index2):
	
    temp = my_list[index1]
    my_list[index1] = my_list[index2]
    my_list[index2] = temp
    
    return my_list
    
def partition(my_list, start, end):
	
    index = start #모든 index를 체크하기 위한 start index
    count = start #Pivot 값보다 큰 수 들의 index & Pivot 보다 작은 수들의 마지막 index
    pivot = end #리스트의 맨끝을 pivot으로 지정
    
    while index < pivot : #리스트의 모든 수를 체크
    	if my_list[index] <= my_list[pivot] :
        	swap_elements(my_list, index, count)
            # 최종적으로 count index는 pivot보다 작은 값들의 리스트의 다음 index이다.
            count += 1
        index += 1
        
    swap_elements(my_list, count, pivot)
    # pivot보다 작은 수들의 리스트의 다음 index와 end에 있는 pivot의 값을 변경
    pivot = count
    
    return pivot
    
def quick_sort(my_list, start, end):
	# 정렬하고자 하는 부분의 길이 : end - start
    # end - start < 1 이라면 정렬이 모두 끝남
    
    if end - start < 1 :
    	return my_list
        
    final_pivot = partition(my_list, start, end)
    
    quick_sort(my_list, start, final_pivot - 1) #pivot보다 작은 수 정렬
    quick_sort(my_list, final_pivot + 1, end ) #pivot보다 큰 수 정렬
    
list1 = [ 1,5,7,3,9,4,6,10,24,8 ]
quick_sort(my_list, 0, len(list1)-1 )
print(list1)

 

* end - start == 0 이면 정렬이 다 끝나지만 if end - start == 0 이 아닌 end - start < 1인 이유 : 

 

my_list = [2,3,4,1] 의 경우 partition(my_list, start, end )의 값으로 pivot은 0이 된다.
quick_sort(my_list, start, pivor-1 )에서 start = 0이고, pivot-1의 값은 -1이므로 
end - start == 0을 만족시키지 못하고 에러가 난다.
즉 pivot 값을 기준으로 모든 리스트의 값들이 pivot 값 보다 클 경우 end - start == 0 을 만족시키지 못한다.

 

# 옵셔널 파라미터

def quick_sort(my_list, start=0, end=None):

    if end == None:
        end = len(my_list) - 1

    if end - start < 1:
        return my_list

    final_pivot = partition(my_list, start, end)
    
    quick_sort(my_list, start, final_pivot - 1)
    quick_sort(my_list, final_pivot + 1, end)
    
    
list1 = [ 1,5,7,3,9,4,6,10,24,8 ]
quick_sort(my_list)
print(list1)

 

* 옵셔널 파라미터 안에는 다른 변수의 값을 가져올 수 없으므로 None이라 지정

 

* 파라미터를 리스트만 받는 quick_sort 함수를 구현할 때 슬라이싱을 사용하면 안되는 이유 :

quick_sort(my_list[:final_pivot])을 하게 되면 my_list가 0부터 final_pivot - 1 까지 복사가 되고

그 복사된 값이 quick_sort 함수안에 들어가는 것이기 때문에 my_list 자체가 정렬이 되지 않는다.