알고리즘) 정렬(4/4) - 퀵소트 & 병합 소트

오늘은 정렬 파트 마지막! 퀵소트와 병합 소트를 해보려고 합니다. 

퀵 소트

퀵소트는 말그대로 빠른 정렬입니다. 

퀵소트는 한 요소를 기준으로(보통 0번째 요소) 해당 요소보다 작은 것은 작은 리스트(왼쪽 리스트)에 더 큰 것은 큰 리스트(오른쪽 리스트)에 넣어요

나눠진 리스트를 또 가지고 와서 똑같이 한 요소를 기준으로 잡고 작은것은 왼쪽에, 더 큰 것은 오른쪽에 배치해서, 리스트의 길이가 1개 남을때까지 반복하다가 다시 그것들을 합치는 것입니다. 커다란 것을 작게작게 쪼개가다가 전체 답을 호로록 구한다는 점에서 분할정복에 해당하고, 계속 같은 함수를 함수 내에서 호출한다는 점에서 재귀용법이 사용되어요(분할정복이 원래 재귀용법을 사용하긴 하지만요ㅎㅎ)

def qsort(data):
	if len(data)<=1:
    	return data
    
    norm = data[0]
    left = [i for i in data[1:] if i < norm]
    right = [i for i in data[1:] if i > norm]
    
    return qsort(left)+[norm]+ qsort(right)

이처럼 반으로 나눈 다음(O(logN), 각 요소들을 합쳐가는 과정O(N)에 의해서 정렬 속도는 O(NlogN)입니다.

그런데 만약 기준이 가장 크거나 가장 작다면 모든 데이터를 비교해야 하기 때문에 O(n^2)가 나올 수도 있습니다. 

병합소트

병합소트도  퀵 소트처럼 큰 부분을 작게 작게 나눠서 전체 문제를 해결하는 분할정복입니다. 퀵소트, 병합소트 둘다 작게 나눠서 합치는 것은 같지만 병합소트는 작게 나눈 상태에서 각잡고 크기를 비교해서 합쳐서 정렬을 이룹니다.

(그래서 그런 관점에서 병합소트의 이름을 그렇게 지었는지도 모르겠네요. 반면 퀵 소트는 어쩌다보니까 정렬이 빠르게 되었네!에 조금 가까운 느낌입니다. )

앞서 말씀드린 것처럼 병합소트는 큰 부분을 계속 반으로 나눠 작은 부품들을 만듭니다. 거의 원소단위에 작은 부품들이 만들어졌을때, 각 요소들의 크기를 비교해서 정렬해 두 요소를 합친 큰 요소를 만듭니다. 다시 위로 올라가서 더 큰 리스트의 요소들끼리 비교해서 정렬한 다음에 전체를 정렬해 나가죠 

def mergeSort(data):
	if len(data)<= 1:
    	return data
    medium = int(len(data)/2))
    part1 = mergeSort(data[:medium])
    part2 = mergetSort(data[medium:])
    return mergeUp(part1, part2)
    
def mergeUp(part1, part2):
	merged = list()
    part1_point, part2_point = 0,0
    
    #만약 part1, part2 모두 데이터가 있을때
    if len(part1) > part1_point and len(part2) > part2_point:
    	if part1[part1_point] > part2[part2_point]:
        	merged.append(part2[part2_point])
            part2_point += 1
        else:
            merged.append(part1[part1_point])
            part1_point += 1
        	
    #만약 part1만 데이터가 남아있다면 : part2 데이터는 다 소진했을 때 
    if len(part1) > part1_point and len(part2) == 0 :
        merged.append(part1[part1_point])
        part1_point += 1
        
    #만약 part2만 데이터가 남아있다면 : part1 데이터는 다 소진했을 때 
    if len(part2) > part2_point and len(part1) == 0 :
        merged.append(part2[part2_point])
        part2_point += 1
        
    return merged

이런 병합정렬또한 반으로 나눠가다가 각 요소끼리 합친다는 점에서 O(nlogN) 의 시간복잡도를 가집니다. 

 

퀵소트와 병합소트는 굉장히 비슷하면서도 다릅니다.

둘 모두 전체를 부분, 부분으로 나눠 들어가 전체 답을 구한다는 점에서 분할정복 방법을 사용해요.

하지만 퀵 소트의 기준은 데이터 맨 앞을 사용한다면, 병합정렬은 기준점이 따로 존재하지 않고 단순히 반으로 나눕니다.(반으로 나누는 지점을 찾기 위해 반으로 나눌 인덱스 지점을 찾긴 하지요)

또 퀵소트는 작게 쪼개는 과정에서 자연스레 정렬이 되어 바로 합칠 수 있는 반면, 병합정렬은 반으로 나눈 다음에 직접 크기를 비교해서 정렬을 만들어 줍니다. 

 

자주 헷갈리는 둘의 개념을 이번에 확실히 해보았습니다!