정렬알고리즘 - Quick Sort (퀵 정렬) | C, Python 코드 구현

이제 재귀함수에 대해 공부했으니 이를 이용해 quick sort를 공부하여 보겠다. Quick Sort. 정렬 알고리즘의 꽃이라고 할 수 있는 알고리즘이다. 공부하면서 정말 quick이라는 말이 왜 붙었는지 알 정도로 이해하기 간단하고 구현하기 굉장히 편리했다. 특히 pythonic code로 구현하니 코드가 아주아주 간결하고 깔끔했다. 코드가 간결할 뿐만 아니라 시간 복잡도 측면에서도 지금까지의 정렬 알고리즘보다 낮아지는 경우가 가능하였다. 살펴보자.

 

📌Quick Sort 퀵 정렬

quick sort는 pivot(기준점)을 정해서, 기준점보다 작은 데이터는 왼쪽에, 큰 데이터는 오른쪽으로 모으는 과정을 반복하여 정렬을 하는 알고리즘이다. 나누어진 왼쪽과 오른쪽이 재귀용법을 사용해서 그 안에서 또 왼쪽과 오른쪽으로 나누는 과정이 반복된다. 함수는 left + pivot + right를 리턴한다.

출처: wekipidia

source: https://runestone.academy/ns/books/published/pythonds/SortSearch/TheQuickSort.html

📌알고리즘 구현 (C)

void quick_sort(int *num_arr, int L, int R){
	int left = L, right = R;
	int pivot = num_arr[(L + R) / 2];

	while (left <= right)
	{
		while (num_arr[left] < pivot)
			left++;
		while (num_arr[right] > pivot)
			right--;
		if (left <= right)
		{
			swap(num_arr, left, right);
			left++;
			right--;
		}
		if (L < right) //아직 끝까지 정렬하지 못함
			quick_sort(num_arr, L, right);
		if (left < R)
			quick_sort(num_arr, left, R);
	}
}

 

📌알고리즘 구현 (python)

def quick_sort(data):
    if len(data) <= 1:
        return data

    left, right = list(), list()
    pivot = data[0]

    for index in range(1, len(data)):
        if pivot > data[index]:
            left.append(data[index])
        else:
            right.append(data[index])

    return quick_sort(left) + [pivot] + quick_sort(right)

pivot = data[0]: 일반적으로 기준점은 맨 앞으로 잡는다.

return quick_sort(left) + pivot + quick_sort(right): 이 부분이 재귀 용법을 사용하는 부분이다. left와 right로 분류를 하고, 그 분류된 left와 right를 다시 quick_sort()함수 안에 넣고, 함수자체는 left와 pivot과 right를 하나의 리스트 안에 넣어 반환하도록 한다.

✚ 좀 더 pythonic한 code로 구현하면... (list comprehension 이용)

def quick_sort(data):
    if len(data) <= 1:
        return data

    pivot = data[0]

    left = [item for item in data[1:] if pivot > item]
    right = [item for item in data[1:] if pivot < item]
    
	return quick_sort(left) + [pivot] + quick_sort(right)

list comprehension을 사용하면 더 깔끔하게 '파이썬스러운pythonic' 코드로 작성할 수 있다. left와 right라는 리스트를 생성과 동시에 조건체크를 하면서 원소를 넣는 것 까지 한줄로 가능하다.

코드가 정말정말 간결해지고 더욱 읽기 쉬워졌다. 이후에 list comprehension을 정리한 글도 포스팅하도록 해봐야겠다...

 

📌시간복잡도

사실, 최악의 경우라면 시간복잡도는 $O(n^2)$이 된다. pivot이 매번 가장 큰 값이거나 가장 작은 값이 되면 모든 데이터를 비교해야하는 상황이 되어버린다. 즉, 이미 정렬이 되어있거나 완전히 역으로 정렬이 되어있다면 매번 pivot이 가장 크거나 작기 때문에 한 쪽 list에 pivot을 제외한 모든 원소가 들어가게 된다. 따라서 데이터가 n개 라면 처음에는 n-1번, n-1번, n-3번 ... 이렇게 계속 비교해야 하므로 시간복잡도는 $O(n^2)$이다.

그러나 일반적인, 평균적인 경우를 생각하여 left와 right가 대략 반반으로 나누어진다고 가정하면 단계수는 $log(n)$이 되기 때문에 시간복잡도는 $O(nlog(n))$이라고 할 수 있다. 일반적인 경우만을 놓고보면 다른 알고리즘들보다 시간복잡도가 낮다고 평가할 수 있다.